/LMAR=0/XLINE=3/FONT#0=BAXL30/FONT#1=BAXM30/FONT#2=BAXB30/FONT#3=SUB/FONT#4=SUP/FONT#5=BASL35/FONT#6=NGR25/FONT#7=MATH30/FONT#8=FIX25/FONT#9=GRK30/FONT#10=ZERO30/FONT#11=BAXI30/FONT#12=MS25



␈↓ ↓H␈↓α␈↓ ¬?HISTORY OF LISP

␈↓ ↓H␈↓␈↓ ¬aJohn McCarthy
␈↓ ↓H␈↓␈↓ ∧rArtificial Intelligence Laboratory
␈↓ ↓H␈↓␈↓ ¬GStanford University




␈↓ ↓H␈↓␈↓↓This␈α∪draft␈α∪gives␈α∪insufficient␈α∪mention␈α∪to␈α∪many␈α∪people␈α∪who␈α∪helped␈α∪implement␈α∪LISP␈α∀and␈α∪who
␈↓ ↓H␈↓↓contributed␈αideas.␈α Suggestions␈αfor␈αimprovements␈α
in␈αthat␈αdirections␈αare␈αparticularly␈αwelcome.␈α
 Facts
␈↓ ↓H␈↓↓about the history of FUNARG and uplevel addressing generally are especially needed␈↓.

␈↓ ↓H␈↓1. Introduction.

␈↓ ↓H␈↓␈↓ α_This␈α∩paper␈α∪concentrates␈α∩on␈α∩the␈α∪development␈α∩of␈α∩the␈α∪basic␈α∩ideas␈α∩and␈α∪distinguishes␈α∩two
␈↓ ↓H␈↓periods␈α-␈αSummer␈α1956␈αthrough␈αSummer␈α1958␈αwhen␈αmost␈αof␈αthe␈αkey␈αideas␈αwere␈αdeveloped␈α(some
␈↓ ↓H␈↓of␈αwhich␈αwere␈αimplemented␈α
in␈αthe␈αFORTRAN␈αbased␈αFLPL),␈α
and␈αFall␈α1958␈αthrough␈α
1962␈αwhen
␈↓ ↓H␈↓the␈α∂programming␈α⊂language␈α∂was␈α∂implemented␈α⊂and␈α∂applied␈α∂to␈α⊂problems␈α∂of␈α⊂artificial␈α∂intelligence.
␈↓ ↓H␈↓After␈α1962,␈αthe␈αdevelopment␈αof␈αLISP␈α
became␈αmulti-stranded,␈αand␈αdifferent␈αideas␈αwere␈αpursued␈α
in
␈↓ ↓H␈↓different places.

␈↓ ↓H␈↓␈↓ α_Except␈αwhere␈αI␈αgive␈αcredit␈αto␈αsomeone␈αelse␈αfor␈αan␈αidea␈αor␈αdecision,␈αI␈αshould␈αbe␈αregarded␈αas
␈↓ ↓H␈↓tentatively␈α⊃claiming␈α⊃credit␈α⊃for␈α⊃it␈α⊃or␈α∩else␈α⊃regarding␈α⊃it␈α⊃as␈α⊃a␈α⊃consequence␈α⊃of␈α∩previous␈α⊃decisions.
␈↓ ↓H␈↓However,␈α∞I␈α
have␈α∞made␈α∞mistakes␈α
about␈α∞such␈α∞matters␈α
in␈α∞the␈α
past,␈α∞and␈α∞I␈α
have␈α∞received␈α∞very␈α
little
␈↓ ↓H␈↓response␈α⊃to␈α⊃requests␈α⊂for␈α⊃comments␈α⊃on␈α⊂drafts␈α⊃of␈α⊃this␈α⊂paper.␈α⊃ It␈α⊃is␈α⊂particularly␈α⊃easy␈α⊃to␈α⊃take␈α⊂as
␈↓ ↓H␈↓obvious␈α∞a␈α∞feature␈α∞that␈α∞cost␈α
someone␈α∞else␈α∞considerable␈α∞thought␈α∞long␈α
ago.␈α∞ As␈α∞the␈α∞writing␈α∞of␈α
this
␈↓ ↓H␈↓paper␈α
approaches␈α
its␈α∞conclusion,␈α
I␈α
have␈α∞become␈α
aware␈α
of␈α∞additional␈α
sources␈α
of␈α∞information␈α
and
␈↓ ↓H␈↓additional areas of uncertainty.

␈↓ ↓H␈↓␈↓ α_As␈αa␈αprogramming␈αlanguage,␈αLISP␈αis␈αcharacterized␈αby␈αthe␈αfollowing␈αideas:␈α computing␈αwith
␈↓ ↓H␈↓symbolic␈α∪expressions␈α∪rather␈α∪than␈α∪numbers,␈α∪representation␈α∪of␈α∪symbolic␈α∪expressions␈α∪and␈α∩other
␈↓ ↓H␈↓information␈α⊃by␈α∩list␈α⊃structure␈α⊃in␈α∩the␈α⊃memory␈α∩of␈α⊃a␈α⊃computer,␈α∩representation␈α⊃of␈α∩information␈α⊃in
␈↓ ↓H␈↓external␈αmedia␈α
mostly␈αby␈αmulti-level␈α
lists␈αand␈αsometimes␈α
by␈αS-expressions,␈αa␈α
small␈αset␈α
of␈αselector
␈↓ ↓H␈↓and␈αconstructor␈αoperations␈αexpressed␈αas␈αfunctions,␈αcomposition␈αof␈αfunctions␈αas␈αa␈αtool␈α
for␈αforming
␈↓ ↓H␈↓more␈α∂complex␈α∂functions,␈α∞the␈α∂use␈α∂of␈α∞conditional␈α∂expressions␈α∂for␈α∞getting␈α∂branching␈α∂into␈α∞function
␈↓ ↓H␈↓definitions,␈α↔the␈α⊗recursive␈α↔use␈α⊗of␈α↔conditional␈α↔expressions␈α⊗as␈α↔a␈α⊗sufficient␈α↔tool␈α↔for␈α⊗building
␈↓ ↓H␈↓computable␈α
functions,␈αthe␈α
use␈αof␈α
λ-expressions␈α
for␈αnaming␈α
functions,␈αthe␈α
representation␈α
of␈αLISP
␈↓ ↓H␈↓programs␈α⊃as␈α⊃LISP␈α⊃data,␈α⊃the␈α⊃conditional␈α⊃expression␈α⊃interpretation␈α⊃of␈α⊃Boolean␈α⊃connectives,␈α⊃the
␈↓ ↓H␈↓LISP␈αfunction␈α␈↓↓eval␈↓␈αthat␈αserves␈αboth␈αas␈αa␈αformal␈αdefinition␈αof␈αthe␈αlanguage␈αand␈αas␈αan␈αinterpreter,
␈↓ ↓H␈↓and␈α∂garbage␈α∞collection␈α∂as␈α∂a␈α∞means␈α∂of␈α∂handling␈α∞the␈α∂erasure␈α∂problem.␈α∞ LISP␈α∂statements␈α∂are␈α∞also
␈↓ ↓H␈↓used as a command language when LISP is used in a time-sharing environment.

␈↓ ↓H␈↓␈↓ α_Some␈α
of␈αthese␈α
ideas␈αwere␈α
taken␈αfrom␈α
other␈αlanguages,␈α
but␈αmost␈α
were␈αnew.␈α
 Towards␈αthe␈α
end
␈↓ ↓H␈↓of␈αthe␈αinitial␈αperiod,␈αit␈αbecame␈αclear␈αthat␈αthis␈αcombination␈αof␈αideas␈αmade␈αan␈αelegant␈αmathematical
␈↓ ↓H␈↓system␈αas␈αwell␈αas␈αa␈αpractical␈αprogramming␈αlanguage.␈α Then␈αmathematical␈αneatness␈αbecame␈αa␈αgoal
␈↓ ↓H␈↓and␈α
led␈α
to␈α
pruning␈α
some␈α
features␈α
from␈α
the␈α
core␈α
of␈α
the␈α
language.␈α
 This␈α
was␈α
partly␈α
motivated␈α
by
␈↓ ↓H␈↓esthetic␈αreasons␈αand␈α
partly␈αby␈αthe␈αbelief␈α
that␈αit␈αwould␈αbe␈α
easier␈αto␈αdevise␈αtechniques␈α
for␈αproving
␈↓ ↓H␈↓␈↓ εH␈↓ 91


␈↓ ↓H␈↓programs␈α↔correct␈α↔if␈α↔the␈α⊗semantics␈α↔were␈α↔compact␈α↔and␈α⊗without␈α↔exceptions.␈α↔ The␈α↔results␈α⊗of
␈↓ ↓H␈↓(Cartwright␈α1976)␈αand␈α(Cartwright␈αand␈αMcCarthy␈α1978),␈αwhich␈αshow␈αthat␈αLISP␈αprograms␈αcan␈αbe
␈↓ ↓H␈↓interpreted␈α∩as␈α∩sentences␈α∩and␈α∪schemata␈α∩of␈α∩first␈α∩order␈α∪logic,␈α∩provide␈α∩new␈α∩confirmation␈α∪of␈α∩the
␈↓ ↓H␈↓original intuition that logical neatness would pay off.

␈↓ ↓H␈↓2. LISP prehistory - Summer 1956 through Summer 1958.

␈↓ ↓H␈↓␈↓ α_My␈α∞desire␈α∞for␈α∂an␈α∞algebraic␈α∞list␈α∂processing␈α∞language␈α∞for␈α∂artificial␈α∞intelligence␈α∞work␈α∂on␈α∞the
␈↓ ↓H␈↓IBM␈α704␈αcomputer␈αarose␈α
in␈αthe␈αsummer␈αof␈α1956␈α
during␈αthe␈αDartmouth␈αSummer␈αResearch␈α
Project
␈↓ ↓H␈↓on␈αArtificial␈αIntelligence␈αwhich␈αwas␈αthe␈αfirst␈αorganized␈αstudy␈αof␈αAI.␈α During␈αthis␈αmeeting,␈αNewell,
␈↓ ↓H␈↓Shaw␈α
and␈α
Simon␈α
described␈α
IPL␈α
2,␈α
a␈α
list␈α
processing␈α
language␈α
for␈α
Rand␈αCorporation's␈α
JOHNNIAC
␈↓ ↓H␈↓computer␈α
in␈α
which␈αthey␈α
implemented␈α
their␈αLogic␈α
Theorist␈α
program.␈α There␈α
was␈α
little␈αtemptation
␈↓ ↓H␈↓to␈αcopy␈αIPL,␈αbecause␈αits␈αform␈αwas␈αbased␈αon␈αa␈αJOHNNIAC␈αloader␈αthat␈αhappened␈αto␈αbe␈αavailable
␈↓ ↓H␈↓to␈α∞them,␈α∞and␈α∞because␈α∞the␈α∞FORTRAN␈α∞idea␈α∞of␈α∞writing␈α∞programs␈α∞algebraically␈α∞was␈α∂attractive.␈α∞ It
␈↓ ↓H␈↓was␈α
immediately␈α
apparent␈αthat␈α
arbitrary␈α
subexpressions␈α
of␈αsymbolic␈α
expressions␈α
could␈αbe␈α
obtained
␈↓ ↓H␈↓by␈α
composing␈α
the␈αfunctions␈α
that␈α
extract␈α
immediate␈αsubexpressions,␈α
and␈α
this␈α
seemed␈αreason␈α
enough
␈↓ ↓H␈↓to go to an algebraic language.

␈↓ ↓H␈↓␈↓ α_There␈α
were␈α
two␈α
motivations␈α
for␈α
developing␈α
a␈αlanguage␈α
for␈α
the␈α
IBM␈α
704.␈α
 First,␈α
IBM␈αhad
␈↓ ↓H␈↓generously␈α
undertaken␈αto␈α
establish␈αa␈α
New␈α
England␈αComputation␈α
Center␈αat␈α
M.I.T.,␈αand␈α
Dartmouth
␈↓ ↓H␈↓would␈α∩be␈α∩able␈α∩to␈α∩use␈α∩it.␈α∩ Second,␈α⊃IBM␈α∩was␈α∩undertaking␈α∩to␈α∩develop␈α∩a␈α∩program␈α∩for␈α⊃proving
␈↓ ↓H␈↓theorems␈α∂in␈α⊂plane␈α∂geometry␈α⊂(based␈α∂on␈α⊂an␈α∂idea␈α⊂of␈α∂Marvin␈α⊂Minsky's),␈α∂and␈α⊂I␈α∂was␈α⊂to␈α∂serve␈α⊂as␈α∂a
␈↓ ↓H␈↓consultant␈α
to␈α
that␈αproject.␈α
 At␈α
the␈αtime,␈α
IBM␈α
looked␈αlike␈α
a␈α
good␈αbet␈α
to␈α
pursue␈αartificial␈α
intelligence
␈↓ ↓H␈↓research␈α∂vigorously,␈α⊂and␈α∂further␈α∂projects␈α⊂were␈α∂expected.␈α⊂ It␈α∂was␈α∂not␈α⊂then␈α∂clear␈α⊂whether␈α∂IBM's
␈↓ ↓H␈↓FORTRAN␈αproject␈αwould␈αlead␈αto␈αa␈αlanguage␈αwithin␈αwhich␈αlist␈αprocessing␈αcould␈α
conveniently␈αbe
␈↓ ↓H␈↓carried␈α
out␈α
or␈α
whether␈α
a␈α
new␈α
language␈α
would␈α
be␈α
required.␈α
 However,␈α
many␈α∞considerations␈α
were
␈↓ ↓H␈↓independent of this decision.

␈↓ ↓H␈↓␈↓ α_Apart␈α
from␈α
consulting␈α
on␈αthe␈α
geometry␈α
program,␈α
my␈αown␈α
research␈α
in␈α
artificial␈αintelligence
␈↓ ↓H␈↓was␈α
proceeding␈α
along␈αthe␈α
lines␈α
that␈αled␈α
to␈α
the␈αAdvice␈α
Taker␈α
proposal␈αin␈α
1958␈α
(McCarthy␈α1959).
␈↓ ↓H␈↓This␈α∀involved␈α∀representing␈α∀information␈α∪about␈α∀the␈α∀world␈α∀by␈α∪sentences␈α∀in␈α∀a␈α∀suitable␈α∪formal
␈↓ ↓H␈↓language␈α
and␈αa␈α
reasoning␈α
program␈αthat␈α
would␈α
decide␈αwhat␈α
to␈α
do␈αby␈α
drawing␈αlogical␈α
consequences.
␈↓ ↓H␈↓Representing␈α∂sentences␈α⊂by␈α∂list␈α∂structure␈α⊂seemed␈α∂appropriate␈α∂-␈α⊂it␈α∂still␈α∂is␈α⊂-␈α∂and␈α∂a␈α⊂list␈α∂processing
␈↓ ↓H␈↓language␈α
also␈α∞seemed␈α
appropriate␈α
for␈α∞programming␈α
the␈α
operations␈α∞involved␈α
in␈α
deduction␈α∞-␈α
and
␈↓ ↓H␈↓still is.

␈↓ ↓H␈↓␈↓ α_This␈α
internal␈α
representation␈α
of␈α
symbolic␈α
information␈α
gives␈α
up␈α
the␈α
familiar␈α
infix␈α
notations␈α
in
␈↓ ↓H␈↓favor␈α∂of␈α∂a␈α∂notation␈α∂that␈α∂simplifies␈α⊂the␈α∂task␈α∂of␈α∂programming␈α∂the␈α∂substantive␈α⊂computations,␈α∂e.g.
␈↓ ↓H␈↓logical␈αdeduction␈αor␈αalgebraic␈αsimplification,␈αdifferentiation␈αor␈αintegration.␈α If␈αcustomary␈αnotations
␈↓ ↓H␈↓are␈αto␈αbe␈αused␈αexternally,␈αtranslation␈αprograms␈αmust␈αbe␈αwritten.␈α Thus␈αmost␈αLISP␈αprograms␈αuse␈αa
␈↓ ↓H␈↓prefix␈α
notation␈α
for␈α
algebraic␈α
expressions,␈α
because␈α
they␈α
usually␈α
must␈α
determine␈α
the␈α
main␈α
connective
␈↓ ↓H␈↓before␈α∀deciding␈α∀what␈α∀to␈α∀do␈α∀next.␈α∃ In␈α∀this␈α∀LISP␈α∀differs␈α∀from␈α∀almost␈α∀every␈α∃other␈α∀symbolic
␈↓ ↓H␈↓computation␈α→system.␈α_ COMIT,␈α→FORMAC,␈α_and␈α→Formula␈α_Algol␈α→programs␈α_all␈α→express␈α_the
␈↓ ↓H␈↓computations␈α∞as␈α∞operations␈α∞on␈α∞some␈α∞approximation␈α∞to␈α∞the␈α∞customary␈α∞printed␈α∞forms␈α∂of␈α∞symbolic
␈↓ ↓H␈↓expressions.␈α SNOBOL␈α
operates␈αon␈α
character␈αstrings␈α
but␈αis␈α
neutral␈αon␈α
how␈αcharacter␈α
strings␈αare
␈↓ ↓H␈↓used␈α⊂to␈α⊂represent␈α⊂symbolic␈α⊂information.␈α⊂ This␈α⊂feature␈α⊂probably␈α⊂accounts␈α⊂for␈α⊂LISP's␈α⊂success␈α⊂in
␈↓ ↓H␈↓competition␈α∪with␈α∪these␈α∪languages,␈α∪especially␈α∪when␈α∪large␈α∪programs␈α∪have␈α∪to␈α∪be␈α∪written.␈α∪ The
␈↓ ↓H␈↓advantage is like that of binary computers over decimal - but larger.
␈↓ ↓H␈↓␈↓ εH␈↓ 92


␈↓ ↓H␈↓(In␈α∪the␈α∩late␈α∪1950s,␈α∩neat␈α∪output␈α∩and␈α∪convenient␈α∩input␈α∪notation␈α∩was␈α∪not␈α∪generally␈α∩considered
␈↓ ↓H␈↓important.␈α
 Programs␈αto␈α
do␈α
the␈αkind␈α
of␈αinput␈α
and␈α
output␈αcustomary␈α
today␈α
wouldn't␈αeven␈α
fit␈αin␈α
the
␈↓ ↓H␈↓memories␈αavailable␈αat␈αthat␈αtime.␈α Moreover,␈αkeypunches␈αand␈αprinters␈αwith␈αadequate␈αcharacter␈αsets
␈↓ ↓H␈↓didn't exist).

␈↓ ↓H␈↓␈↓ α_The␈αfirst␈α
problem␈αwas␈α
how␈αto␈α
do␈αlist␈α
structure␈αin␈α
the␈αIBM␈α
704.␈α This␈α
computer␈αhas␈α
a␈α36␈α
bit
␈↓ ↓H␈↓word,␈α⊃and␈α⊃two␈α⊃15␈α⊃bit␈α⊃parts,␈α⊃called␈α⊃the␈α⊃address␈α⊃and␈α⊃decrement,␈α⊃were␈α⊃distinguished␈α∩by␈α⊃special
␈↓ ↓H␈↓instructions␈αfor␈αmoving␈αtheir␈αcontents␈αto␈αand␈αfrom␈αthe␈α15␈αbit␈αindex␈αregisters.␈α The␈αaddress␈αof␈αthe
␈↓ ↓H␈↓machine␈α
was␈α
15␈α
bits,␈α
so␈α
it␈α
was␈α
clear␈α
that␈α
list␈α
structure␈α
should␈α
use␈α
15␈α
bit␈α
pointers.␈α
 Therefore,␈α
it␈α
was
␈↓ ↓H␈↓natural␈α∞to␈α∞consider␈α∂the␈α∞word␈α∞as␈α∞divided␈α∂into␈α∞4␈α∞parts,␈α∞the␈α∂address␈α∞part,␈α∞the␈α∞decrement␈α∂part,␈α∞the
␈↓ ↓H␈↓prefix␈αpart␈αand␈α
the␈αtag␈αpart.␈α
 The␈αlast␈αtwo␈α
were␈αthree␈αbits␈α
each␈αand␈αseparated␈α
from␈αeach␈αother␈α
by
␈↓ ↓H␈↓the decrement so that they could not be easily combined into a single six bit part.

␈↓ ↓H␈↓␈↓ α_At␈αthis␈αpoint␈αthere␈αwas␈αsome␈α
indecision␈αabout␈αwhat␈αthe␈αbasic␈αoperators␈αshould␈α
be,␈αbecause
␈↓ ↓H␈↓the␈α∞operation␈α∂of␈α∞extracting␈α∞a␈α∂part␈α∞of␈α∞the␈α∂word␈α∞by␈α∞masking␈α∂was␈α∞considered␈α∞separately␈α∂from␈α∞the
␈↓ ↓H␈↓operation␈αof␈αtaking␈αthe␈αcontents␈αof␈αa␈αword␈αin␈α
memory␈αas␈αa␈αfunction␈αof␈αits␈αaddress.␈α At␈αthe␈αtime,␈α
it
␈↓ ↓H␈↓seemed␈α⊂dubious␈α⊂to␈α⊂regard␈α⊂the␈α⊂latter␈α⊂operation␈α⊂as␈α⊂a␈α⊂function,␈α⊂since␈α⊂its␈α⊂value␈α⊂depended␈α⊂on␈α∂the
␈↓ ↓H␈↓contents␈α⊃of␈α∩memory␈α⊃at␈α∩the␈α⊃time␈α∩the␈α⊃operation␈α⊃was␈α∩performed,␈α⊃so␈α∩it␈α⊃didn't␈α∩act␈α⊃like␈α∩a␈α⊃proper
␈↓ ↓H␈↓mathematical␈α
function.␈α
 However,␈α
the␈α
advantages␈α
of␈αtreating␈α
it␈α
grammatically␈α
as␈α
a␈α
function␈αso␈α
that
␈↓ ↓H␈↓it could be composed were also apparent.

␈↓ ↓H␈↓␈↓ α_Therefore,␈α
the␈αinitially␈α
proposed␈α
set␈αof␈α
functions␈αincluded␈α
␈↓↓cwr␈↓,␈α
standing␈αfor␈α
"Contents␈αof␈α
the
␈↓ ↓H␈↓Word␈α
in␈α∞Register␈α
number"␈α∞and␈α
four␈α∞functions␈α
that␈α∞extracted␈α
the␈α∞parts␈α
of␈α∞the␈α
word␈α∞and␈α
shifted
␈↓ ↓H␈↓them␈αto␈αa␈αstandard␈αposition␈αat␈αthe␈αright␈αof␈αthe␈αword.␈α An␈αadditional␈αfunction␈αof␈αthree␈αarguments
␈↓ ↓H␈↓that would also extract an arbitrary bit sequence was also proposed.

␈↓ ↓H␈↓␈↓ α_It␈αwas␈αsoon␈αnoticed␈αthat␈αextraction␈α
of␈αa␈αsubexpression␈αinvolved␈αcomposing␈αthe␈αextraction␈α
of
␈↓ ↓H␈↓the␈αaddress␈αpart␈αwith␈α␈↓↓cwr␈↓␈αand␈αthat␈αcontinuing␈αalong␈αthe␈αlist␈αinvolved␈αcomposing␈αthe␈αextraction␈αof
␈↓ ↓H␈↓the␈α∩decrement␈α∩part␈α∪with␈α∩␈↓↓cwr␈↓.␈α∩ Therefore,␈α∪the␈α∩compounds␈α∩␈↓↓car␈↓,␈α∪standing␈α∩for␈α∩"Contents␈α∪of␈α∩the
␈↓ ↓H␈↓Address␈αpart␈αof␈αRegister␈αnumber",␈α
and␈αits␈αanalogs␈α␈↓↓cdr␈↓,␈α␈↓↓cpr␈↓,␈α
and␈α␈↓↓ctr␈↓␈αwere␈αdefined.␈α The␈α
motivation
␈↓ ↓H␈↓for␈α∞implementing␈α
␈↓↓car␈↓␈α∞and␈α
␈↓↓cdr␈↓␈α∞separately␈α
was␈α∞strengthened␈α
by␈α∞the␈α
vulgar␈α∞fact␈α
that␈α∞the␈α∞IBM␈α
704
␈↓ ↓H␈↓had␈α⊃instructions␈α⊃(connected␈α⊂with␈α⊃indexing)␈α⊃that␈α⊂made␈α⊃these␈α⊃operations␈α⊂easy␈α⊃to␈α⊃implement.␈α⊂ A
␈↓ ↓H␈↓construct␈αoperation␈αfor␈αtaking␈αa␈αword␈αoff␈α
the␈αfree␈αstorage␈αlist␈αand␈αstuffing␈αit␈αwith␈α
given␈αcontents
␈↓ ↓H␈↓was␈α
also␈α
obviously␈αrequired.␈α
 At␈α
some␈α
point␈αa␈α
␈↓↓cons(a,d,p,t)␈↓␈α
was␈α
defined,␈αbut␈α
it␈α
was␈α
regarded␈αas␈α
a
␈↓ ↓H␈↓subroutine␈αand␈αnot␈αas␈αa␈αfunction␈αwith␈αa␈αvalue.␈α This␈αwork␈αwas␈αdone␈αat␈αDartmouth,␈αbut␈αnot␈αon␈αa
␈↓ ↓H␈↓computer,␈α
since␈α
the␈α
New␈α
England␈α
Computation␈α
Center␈α
was␈α
not␈α
expected␈α
to␈α
receive␈α
its␈α∞IBM␈α
704
␈↓ ↓H␈↓for another year.

␈↓ ↓H␈↓␈↓ α_In␈α⊗connection␈α⊗with␈α∃IBM's␈α⊗plane␈α⊗geometry␈α∃project,␈α⊗Nathaniel␈α⊗Rochester␈α⊗and␈α∃Herbert
␈↓ ↓H␈↓Gelernter␈α∂(on␈α∂the␈α∞advice␈α∂of␈α∂McCarthy)␈α∞decided␈α∂to␈α∂implement␈α∞a␈α∂list␈α∂processing␈α∂language␈α∞within
␈↓ ↓H␈↓FORTRAN,␈α
because␈α
this␈α
seemed␈αto␈α
the␈α
the␈α
easiest␈αway␈α
to␈α
get␈α
started,␈αand,␈α
in␈α
those␈α
days,␈αwriting␈α
a
␈↓ ↓H␈↓compiler␈α
for␈α
a␈α
new␈α
language␈α
was␈α
believed␈α
to␈α
take␈α
many␈α
man-years.␈α
 This␈α
work␈α
was␈α
undertaken␈α
by
␈↓ ↓H␈↓Herbert␈α
Gelernter␈α
and␈α
Carl␈α∞Gerberich␈α
at␈α
IBM␈α
and␈α
led␈α∞to␈α
FLPL,␈α
standing␈α
for␈α∞FORTRAN␈α
List
␈↓ ↓H␈↓Processing␈αLanguage.␈α Gelernter␈αand␈αGerberich␈αnoticed␈αthat␈α␈↓↓cons␈↓␈αshould␈αbe␈αa␈αfunction,␈αnot␈αjust␈αa
␈↓ ↓H␈↓subroutine,␈α
and␈α
that␈α
its␈α
value␈αshould␈α
be␈α
the␈α
location␈α
of␈α
the␈αword␈α
that␈α
had␈α
been␈α
taken␈α
from␈αthe
␈↓ ↓H␈↓free␈α
storage␈α∞list.␈α
 This␈α∞permitted␈α
new␈α∞expressions␈α
to␈α∞be␈α
constructed␈α∞out␈α
of␈α∞subsubexpressions␈α
by
␈↓ ↓H␈↓composing occurrences of ␈↓↓cons␈↓.
␈↓ ↓H␈↓␈↓ εH␈↓ 93


␈↓ ↓H␈↓␈↓ α_While␈α∞expressions␈α∞could␈α∞be␈α∞handled␈α∞easily␈α∞in␈α∞FLPL,␈α∞and␈α∞it␈α∞was␈α∞used␈α∞successfully␈α∞for␈α∞the
␈↓ ↓H␈↓Geometry␈αprogram,␈αit␈αhad␈αneither␈αconditional␈αexpressions␈αnor␈αrecursion,␈αand␈αerasing␈αlist␈αstructure
␈↓ ↓H␈↓was handled explicitly by the program.

␈↓ ↓H␈↓␈↓ α_I␈α
invented␈α∞conditional␈α
expressions␈α∞in␈α
connection␈α∞with␈α
a␈α
set␈α∞of␈α
chess␈α∞legal␈α
move␈α∞routines␈α
I
␈↓ ↓H␈↓wrote␈αin␈αFORTRAN␈αfor␈αthe␈α
IBM␈α704␈αat␈αM.I.T.␈αduring␈α
1957-58.␈α This␈αprogram␈αdid␈αnot␈α
use␈αlist
␈↓ ↓H␈↓processing.␈α
 The␈αIF␈α
statement␈α
provided␈αin␈α
FORTRAN␈α
1␈αand␈α
FORTRAN␈α
2␈αwas␈α
very␈αawkward␈α
to
␈↓ ↓H␈↓use,␈αand␈αit␈αwas␈αnatural␈αto␈αinvent␈αa␈αfunction␈αXIF(M,N1,N2)␈αwhose␈αvalue␈αwas␈αN1␈αor␈αN2␈αaccording
␈↓ ↓H␈↓to␈αwhether␈αthe␈αexpression␈αM␈αwas␈αzero␈αor␈αnot.␈α The␈αfunction␈αshortened␈αmany␈αprograms␈αand␈αmade
␈↓ ↓H␈↓them␈αeasier␈αto␈αunderstand,␈αbut␈αit␈αhad␈αto␈αbe␈αused␈αsparingly,␈αbecause␈αall␈αthree␈αarguments␈αhad␈αto␈αbe
␈↓ ↓H␈↓evaluated␈α⊂before␈α∂XIF␈α⊂was␈α⊂entered,␈α∂since␈α⊂XIF␈α∂was␈α⊂called␈α⊂as␈α∂an␈α⊂ordinary␈α⊂FORTRAN␈α∂function
␈↓ ↓H␈↓though␈αwritten␈αin␈αmachine␈αlanguage.␈α This␈αled␈α
to␈αthe␈αinvention␈αof␈αthe␈αtrue␈αconditional␈α
expression
␈↓ ↓H␈↓which␈αevaluates␈αonly␈αone␈α
of␈αN1␈αand␈αN2␈αaccording␈α
to␈αwhether␈αM␈αis␈αtrue␈α
or␈αfalse␈αand␈αto␈α
a␈αdesire
␈↓ ↓H␈↓for a programming language that would allow its use.

␈↓ ↓H␈↓␈↓ α_A␈αpaper␈αdefining␈αconditional␈αexpressions␈αand␈αproposing␈αtheir␈αuse␈αin␈αAlgol␈αwas␈αsent␈α
to␈αthe
␈↓ ↓H␈↓␈↓↓Communications␈α
of␈α
the␈α
ACM␈↓␈αbut␈α
was␈α
arbitrarily␈α
demoted␈αto␈α
a␈α
letter␈α
to␈αthe␈α
editor,␈α
because␈α
it␈αwas
␈↓ ↓H␈↓very short.

␈↓ ↓H␈↓␈↓ α_I␈αspent␈αthe␈αsummer␈αof␈α1958␈αat␈αthe␈αIBM␈αInformation␈αResearch␈αDepartment␈αat␈αthe␈αinvitation
␈↓ ↓H␈↓of␈α∞Nathaniel␈α∞Rochester␈α
and␈α∞chose␈α∞differentiating␈α
algebraic␈α∞expressions␈α∞as␈α
a␈α∞sample␈α∞problem.␈α
 It
␈↓ ↓H␈↓led to the following innovations beyond FLPL:

␈↓ ↓H␈↓␈↓ α_a.␈α∃Writing␈α∃recursive␈α∃function␈α∃definitions␈α∃using␈α∃conditional␈α∃expressions.␈α∃ The␈α∃idea␈α∀of
␈↓ ↓H␈↓differentiation␈α⊂is␈α⊂obviously␈α∂recursive,␈α⊂and␈α⊂conditional␈α∂expressions␈α⊂allowed␈α⊂combining␈α⊂the␈α∂cases
␈↓ ↓H␈↓into a single formula.

␈↓ ↓H␈↓␈↓ α_b.␈α∞The␈α∞␈↓↓maplist␈↓␈α∞function␈α∞that␈α∞forms␈α∞a␈α
list␈α∞of␈α∞applications␈α∞of␈α∞a␈α∞functional␈α∞argument␈α∞to␈α
the
␈↓ ↓H␈↓elements␈αof␈αa␈αlist.␈α This␈αwas␈αobviously␈αwanted␈αfor␈αdifferentiating␈αsums␈αof␈αarbitrarily␈αmany␈αterms,
␈↓ ↓H␈↓and␈αwith␈α
a␈αslight␈α
modification,␈αit␈α
could␈αbe␈α
applied␈αto␈α
differentiating␈αproducts.␈α
 (The␈αoriginal␈α
form
␈↓ ↓H␈↓was what is now called ␈↓↓mapcar␈↓).

␈↓ ↓H␈↓␈↓ α_c.␈αTo␈αuse␈αfunctions␈αas␈αarguments,␈αone␈αneeds␈αa␈αnotation␈αfor␈αfunctions,␈αand␈αit␈αseemed␈αnatural
␈↓ ↓H␈↓to␈α∂use␈α∂the␈α∂λ-notation␈α∂of␈α∂Church␈α∂(1941).␈α∂ I␈α∂didn't␈α∂understand␈α∂the␈α∂rest␈α∂of␈α∂his␈α∂book,␈α∂so␈α∂I␈α∂wasn't
␈↓ ↓H␈↓tempted␈α∞to␈α∞try␈α∂to␈α∞implement␈α∞his␈α∂more␈α∞general␈α∞mechanism␈α∂for␈α∞defining␈α∞functions.␈α∂ Church␈α∞used
␈↓ ↓H␈↓higher␈α⊂order␈α∂functionals␈α⊂instead␈α∂of␈α⊂using␈α∂conditional␈α⊂expressions.␈α∂ Conditional␈α⊂expressions␈α∂are
␈↓ ↓H␈↓much more readily implemented on computers.

␈↓ ↓H␈↓␈↓ α_d.␈αThe␈αrecursive␈αdefinition␈αof␈α
differentiation␈αmade␈αno␈αprovision␈αfor␈αerasure␈α
of␈αabandoned
␈↓ ↓H␈↓list␈α⊂structure.␈α∂ No␈α⊂solution␈α∂was␈α⊂apparent␈α∂at␈α⊂the␈α∂time,␈α⊂but␈α∂the␈α⊂idea␈α∂of␈α⊂complicating␈α⊂the␈α∂elegant
␈↓ ↓H␈↓definition␈α
of␈α
differentiation␈α
with␈α
explicit␈α
erasure␈α
was␈α
unattractive.␈α
 Needless␈α
to␈α
say,␈α
the␈α
point␈αof
␈↓ ↓H␈↓the␈αexercise␈αwas␈αnot␈αthe␈αdifferentiation␈αprogram␈αitself,␈αseveral␈αof␈αwhich␈αhad␈αalready␈αbeen␈αwritten,
␈↓ ↓H␈↓but rather clarification of the operations involved in symbolic computation.

␈↓ ↓H␈↓␈↓ α_In␈α∩fact,␈α∩the␈α∩differentiation␈α∩program␈α∩was␈α∩not␈α∩implemented␈α∩that␈α∩summer,␈α∩because␈α⊃FLPL
␈↓ ↓H␈↓allows␈α⊃neither␈α⊃conditional␈α⊃expressions␈α⊂nor␈α⊃recursive␈α⊃use␈α⊃of␈α⊂subroutines.␈α⊃ At␈α⊃this␈α⊃point␈α⊃a␈α⊂new
␈↓ ↓H␈↓language␈α
was␈α
necessary,␈α
since␈α
it␈α
was␈α∞very␈α
difficult␈α
both␈α
technically␈α
and␈α
politically␈α
to␈α∞tinker␈α
with
␈↓ ↓H␈↓Fortran,␈α∞and␈α∞neither␈α∂conditional␈α∞expressions␈α∞nor␈α∞recursion␈α∂could␈α∞be␈α∞implemented␈α∂with␈α∞machine
␈↓ ↓H␈↓␈↓ εH␈↓ 94


␈↓ ↓H␈↓language␈α⊂Fortran␈α⊂functions␈α⊂-␈α⊂not␈α⊂even␈α⊂with␈α⊂"functions"␈α⊂that␈α⊂modify␈α⊂the␈α⊂code␈α⊂that␈α⊂calls␈α⊂them.
␈↓ ↓H␈↓Moreover,␈α
the␈α
IBM␈α
group␈α
seemed␈α
satisfied␈α
with␈α
FLPL␈α
as␈α
it␈α
was␈α
and␈α
did␈α
not␈α
want␈α
to␈α
make␈α
the
␈↓ ↓H␈↓vaguely␈α∀stated␈α∪but␈α∀obviously␈α∀drastic␈α∪changes␈α∀required␈α∀to␈α∪allow␈α∀conditional␈α∀expressions␈α∪and
␈↓ ↓H␈↓recursive definition.  As I recall, they argued that these were unnecessary.

␈↓ ↓H␈↓2. The implementation of LISP.

␈↓ ↓H␈↓␈↓ α_In␈α∞the␈α∞Fall␈α∂of␈α∞1958,␈α∞I␈α∂became␈α∞Assistant␈α∞Professor␈α∞of␈α∂Communication␈α∞Sciences␈α∞(in␈α∂the␈α∞EE
␈↓ ↓H␈↓Department)␈α∩at␈α∩M.I.T.,␈α⊃and␈α∩Marvin␈α∩Minsky␈α⊃(then␈α∩an␈α∩assistant␈α⊃professor␈α∩in␈α∩the␈α⊃Mathematics
␈↓ ↓H␈↓Department)␈α
and␈α∞I␈α
started␈α
the␈α∞M.I.T.␈α
Artificial␈α
Intelligence␈α∞Project.␈α
 The␈α
Project␈α∞was␈α
supported
␈↓ ↓H␈↓by␈α
the␈α
M.I.T.␈α
Research␈αLaboratory␈α
of␈α
Electronics␈α
which␈α
had␈αa␈α
contract␈α
from␈α
the␈α
armed␈αservices
␈↓ ↓H␈↓that␈αpermitted␈αgreat␈αfreedom␈αto␈αthe␈αDirector,␈αProfessor␈αJerome␈αWiesner,␈αin␈αinitiating␈αnew␈αprojects
␈↓ ↓H␈↓that␈α∂seemed␈α∞to␈α∂him␈α∂of␈α∞scientific␈α∂interest.␈α∂ No␈α∞written␈α∂proposal␈α∂was␈α∞ever␈α∂made.␈α∂ When␈α∞Wiesner
␈↓ ↓H␈↓asked␈αMinsky␈αand␈αme␈αwhat␈αwe␈αneeded␈αfor␈αthe␈αproject,␈αwe␈αasked␈αfor␈αa␈αroom,␈αtwo␈αprogrammers,␈αa
␈↓ ↓H␈↓secretary␈α
and␈αa␈α
keypunch,␈αand␈α
he␈αasked␈α
us␈αto␈α
also␈αundertake␈α
the␈αsupervision␈α
of␈αsome␈α
of␈α
the␈αsix
␈↓ ↓H␈↓mathematics graduate students that R.L.E. had undertaken to support.

␈↓ ↓H␈↓␈↓ α_The␈α⊂implementation␈α⊂of␈α⊃LISP␈α⊂began␈α⊂in␈α⊃Fall␈α⊂1958.␈α⊂ The␈α⊂original␈α⊃idea␈α⊂was␈α⊂to␈α⊃produce␈α⊂a
␈↓ ↓H␈↓compiler,␈α∂but␈α∞this␈α∂was␈α∞considered␈α∂a␈α∞major␈α∂undertaking,␈α∞and␈α∂we␈α∞needed␈α∂some␈α∂experimenting␈α∞in
␈↓ ↓H␈↓order␈αto␈αget␈αgood␈αconventions␈αfor␈αsubroutine␈αlinking,␈αstack␈αhandling␈αand␈αerasure.␈α
 Therefore,␈αwe
␈↓ ↓H␈↓started␈α∞by␈α∞hand-compiling␈α
various␈α∞functions␈α∞into␈α∞assembly␈α
language␈α∞and␈α∞writing␈α∞subroutines␈α
to
␈↓ ↓H␈↓provide␈αa␈αLISP␈α"environment".␈α These␈αincluded␈αprograms␈αto␈αread␈αand␈αprint␈αlist␈αstructure.␈α I␈αcan't
␈↓ ↓H␈↓now␈α∂remember␈α∂whether␈α∂the␈α∂decision␈α∂to␈α∂use␈α∂parenthesized␈α∂list␈α∂notation␈α∂as␈α∂the␈α∂external␈α∂form␈α∞of
␈↓ ↓H␈↓LISP␈α∀data␈α∀was␈α∀made␈α∃then␈α∀or␈α∀whether␈α∀it␈α∀had␈α∃already␈α∀been␈α∀used␈α∀in␈α∀discussing␈α∃the␈α∀paper
␈↓ ↓H␈↓differentiation program.

␈↓ ↓H␈↓␈↓ α_The␈α∀programs␈α∪to␈α∀be␈α∪hand-compiled␈α∀were␈α∀written␈α∪in␈α∀an␈α∪informal␈α∀notation␈α∀called␈α∪M-
␈↓ ↓H␈↓expressions␈α⊃intended␈α⊃to␈α∩resemble␈α⊃FORTRAN␈α⊃as␈α∩much␈α⊃as␈α⊃possible.␈α∩ Besides␈α⊃FORTRAN-like
␈↓ ↓H␈↓assignment␈α⊂statements␈α⊃and␈α⊂␈↓αgo to␈↓s,␈α⊂the␈α⊃language␈α⊂allowed␈α⊂conditional␈α⊃expressions␈α⊂and␈α⊃the␈α⊂basic
␈↓ ↓H␈↓functions␈α∂of␈α∞LISP.␈α∂ Allowing␈α∞recursive␈α∂function␈α∞definitions␈α∂required␈α∞no␈α∂new␈α∞notation␈α∂from␈α∞the
␈↓ ↓H␈↓function␈α
definitions␈α
allowed␈α∞in␈α
FORTRAN␈α
I␈α
-␈α∞only␈α
the␈α
removal␈α
of␈α∞the␈α
restriction␈α
-␈α
as␈α∞I␈α
recall,
␈↓ ↓H␈↓unstated␈α⊂in␈α⊂the␈α⊂FORTRAN␈α⊂manual␈α⊂-␈α⊂forbidding␈α⊂recursive␈α⊂definitions.␈α⊂ The␈α⊃M-notation␈α⊂also
␈↓ ↓H␈↓used␈α∂brackets␈α∂instead␈α∂of␈α∂parentheses␈α∂to␈α∂enclose␈α∂the␈α∂arguments␈α∂of␈α∂functions␈α∂in␈α∂order␈α⊂to␈α∂reserve
␈↓ ↓H␈↓parentheses␈α
for␈α
list-structure␈α
constants.␈α
 It␈α
was␈α
intended␈α
to␈α
compile␈α
from␈α
some␈α∞approximation␈α
to
␈↓ ↓H␈↓the␈αM-notation,␈αbut␈αthe␈αM-notation␈αwas␈αnever␈αfully␈αdefined,␈αbecause␈αrepresenting␈αLISP␈α
functions
␈↓ ↓H␈↓by␈α⊂LISP␈α⊂lists␈α⊂became␈α⊂the␈α⊂dominant␈α∂programming␈α⊂language␈α⊂when␈α⊂the␈α⊂interpreter␈α⊂later␈α∂became
␈↓ ↓H␈↓available.␈α A␈αmachine␈αreadable␈αM-notation␈αwould␈αhave␈αrequired␈αredefinition,␈αbecause␈αthe␈α
pencil-
␈↓ ↓H␈↓and-paper M-notation used characters unavailable on the IBM 026 key punch.

␈↓ ↓H␈↓␈↓ α_The␈α∩READ␈α∪and␈α∩PRINT␈α∪programs␈α∩induced␈α∩a␈α∪␈↓↓de␈α∩facto␈↓␈α∪standard␈α∩external␈α∪notation␈α∩for
␈↓ ↓H␈↓symbolic␈α%information,␈α$e.g.␈α%representing␈α$␈↓↓x + 3y + z␈↓␈α%by␈α%(PLUS X (TIMES 3 Y) Z)␈α$and
␈↓ ↓H␈↓␈↓↓(∀x)(P(x)∨Q(x,y))␈↓␈α∪by␈α∪(ALL (X) (OR (P X) (Q X Y))).␈α∩ Any␈α∪other␈α∪notation␈α∪necessarily␈α∩requires
␈↓ ↓H␈↓special␈α⊗programming,␈α⊗because␈α⊗standard␈α↔mathematical␈α⊗notations␈α⊗treat␈α⊗different␈α↔operators␈α⊗in
␈↓ ↓H␈↓syntactically␈αdifferent␈αways.␈α This␈αnotation␈αlater␈αcame␈αto␈αbe␈αcalled␈α"Cambridge␈αPolish",␈αbecause␈αit
␈↓ ↓H␈↓resembled␈αthe␈αprefix␈αnotation␈αof␈α
Lukasiewicz,␈αand␈αbecause␈αwe␈αnoticed␈α
that␈αQuine␈αhad␈αalso␈αused␈α
a
␈↓ ↓H␈↓parenthesized prefix notation.

␈↓ ↓H␈↓␈↓ α_The␈α
erasure␈α
problem␈αalso␈α
had␈α
to␈α
be␈αconsidered,␈α
and␈α
it␈α
was␈αclearly␈α
unaesthetic␈α
to␈αuse␈α
explicit
␈↓ ↓H␈↓␈↓ εH␈↓ 95


␈↓ ↓H␈↓erasure␈α∞as␈α∞did␈α∞IPL.␈α∞ There␈α∞were␈α∞two␈α∞alternatives.␈α∞ The␈α∞first␈α∞was␈α∞to␈α∞erase␈α∞the␈α∞old␈α∞contents␈α∂of␈α∞a
␈↓ ↓H␈↓program␈α∞variable␈α∞whenever␈α
it␈α∞was␈α∞updated.␈α
 Since␈α∞the␈α∞␈↓↓car␈↓␈α
and␈α∞␈↓↓cdr␈↓␈α∞operations␈α
were␈α∞not␈α∞to␈α
copy
␈↓ ↓H␈↓structure,␈α⊂merging␈α⊂list␈α∂structure␈α⊂would␈α⊂occur,␈α∂and␈α⊂erasure␈α⊂would␈α∂require␈α⊂a␈α⊂system␈α⊂of␈α∂reference
␈↓ ↓H␈↓counts.␈α∞ Since␈α∞there␈α∞were␈α∞only␈α∞six␈α∞bits␈α∞left␈α∞in␈α∞a␈α∞word,␈α∞and␈α∞these␈α∞were␈α∞in␈α∞separated␈α∞parts␈α∞of␈α
the
␈↓ ↓H␈↓word,␈α
reference␈αcounts␈α
seemed␈αinfeasible␈α
without␈αa␈α
drastic␈αchange␈α
in␈αthe␈α
way␈αlist␈α
structures␈αwere
␈↓ ↓H␈↓represented.␈α (A␈αlist␈αhandling␈αscheme␈αusing␈αreference␈αcounts␈αwas␈αlater␈αused␈αby␈αCollins␈α(1960)␈αon␈αa
␈↓ ↓H␈↓48 bit CDC computer).

␈↓ ↓H␈↓␈↓ α_The␈α∞second␈α∂alternative␈α∞is␈α∂␈↓↓garbage␈α∞collection␈↓␈α∂in␈α∞which␈α∂storage␈α∞is␈α∂abandoned␈α∞until␈α∂the␈α∞free
␈↓ ↓H␈↓storage␈α
list␈α
is␈α
exhausted,␈α
the␈α
storage␈α
accessible␈α
from␈α
program␈α
variables␈α
and␈α
the␈α
stack␈α
is␈α
marked,
␈↓ ↓H␈↓and␈α∂the␈α∂unmarked␈α∂storage␈α∂is␈α∂made␈α∂into␈α∂a␈α∂new␈α∂free␈α∂storage␈α∂list.␈α∂ Once␈α∂we␈α∂decided␈α∂on␈α∞garbage
␈↓ ↓H␈↓collection,␈α∂its␈α∂actual␈α∂implementation␈α∂could␈α∂be␈α∞postponed,␈α∂because␈α∂only␈α∂toy␈α∂examples␈α∂were␈α∞being
␈↓ ↓H␈↓done.

␈↓ ↓H␈↓␈↓ α_At␈α∂that␈α∞time␈α∂it␈α∞was␈α∂also␈α∞decided␈α∂to␈α∞use␈α∂SAVE␈α∞and␈α∂UNSAVE␈α∞routines␈α∂that␈α∞use␈α∂a␈α∞single
␈↓ ↓H␈↓contiguous␈α
public␈αstack␈α
array␈αto␈α
save␈α
the␈αvalues␈α
of␈αvariables␈α
and␈αsubroutine␈α
return␈α
addresses␈αin
␈↓ ↓H␈↓the␈α
implementation␈α
of␈α
recursive␈α
subroutines.␈α
 IPL␈α
built␈α
stacks␈α
as␈α
list␈α
structure␈α
and␈α
their␈α
use␈α
had␈α
to
␈↓ ↓H␈↓be␈αexplicitly␈αprogrammed.␈α Another␈αdecision␈αwas␈αto␈αgive␈αup␈αthe␈αprefix␈αand␈αtag␈αparts␈αof␈αthe␈αword,
␈↓ ↓H␈↓to␈α
abandon␈α
␈↓↓cwr␈↓,␈α
and␈αto␈α
make␈α
␈↓↓cons␈↓␈α
a␈α
function␈αof␈α
two␈α
arguments.␈α
 This␈αleft␈α
us␈α
with␈α
only␈α
a␈αsingle
␈↓ ↓H␈↓type - the 15 bit address - so that the language didn't require declarations.

␈↓ ↓H␈↓␈↓ α_These␈α⊃simplifications␈α⊃made␈α∩LISP␈α⊃into␈α⊃a␈α⊃way␈α∩of␈α⊃describing␈α⊃computable␈α∩functions␈α⊃much
␈↓ ↓H␈↓neater␈α
than␈α
the␈α
Turing␈α
machines␈α
or␈α
the␈α
general␈α
recursive␈α
definitions␈α
used␈α
in␈α∞recursive␈α
function
␈↓ ↓H␈↓theory.␈α⊂ The␈α∂fact␈α⊂that␈α∂Turing␈α⊂machines␈α∂constitute␈α⊂an␈α∂awkward␈α⊂programming␈α⊂language␈α∂doesn't
␈↓ ↓H␈↓much␈α⊂bother␈α∂recursive␈α⊂function␈α⊂theorists,␈α∂because␈α⊂they␈α∂almost␈α⊂never␈α⊂have␈α∂any␈α⊂reason␈α⊂to␈α∂write
␈↓ ↓H␈↓particular␈α∂recursive␈α∂definitions,␈α∂since␈α∂the␈α∂theory␈α∂concerns␈α∂recursive␈α∂functions␈α∂in␈α⊂general.␈α∂ They
␈↓ ↓H␈↓often␈αhave␈αreason␈αto␈αprove␈αthat␈αrecursive␈αfunctions␈αwith␈αspecific␈αproperties␈αexist,␈αbut␈αthis␈αcan␈αbe
␈↓ ↓H␈↓done␈α
by␈αan␈α
informal␈α
argument␈αwithout␈α
having␈αto␈α
write␈α
them␈αdown␈α
explicitly.␈α
 In␈αthe␈α
early␈αdays␈α
of
␈↓ ↓H␈↓computing,␈αsome␈αpeople␈α
developed␈αprogramming␈αlanguages␈αbased␈α
on␈αTuring␈αmachines;␈αperhaps␈α
it
␈↓ ↓H␈↓seemed␈α∃more␈α⊗scientific.␈α∃ Anyway,␈α⊗I␈α∃decided␈α⊗to␈α∃write␈α∃a␈α⊗paper␈α∃describing␈α⊗LISP␈α∃both␈α⊗as␈α∃a
␈↓ ↓H␈↓programming␈α
language␈α
and␈αas␈α
a␈α
formalism␈αfor␈α
doing␈α
recursive␈αfunction␈α
theory.␈α
 The␈α
paper␈αwas
␈↓ ↓H␈↓␈↓↓Recursive␈α∞functions␈α
of␈α∞symbolic␈α
expressions␈α∞and␈α∞their␈α
computation␈α∞by␈α
machine,␈α∞part␈α∞I␈↓␈α
(McCarthy
␈↓ ↓H␈↓1960).␈α⊂ Part␈α∂II␈α⊂was␈α∂never␈α⊂written␈α⊂but␈α∂was␈α⊂intended␈α∂to␈α⊂contain␈α∂applications␈α⊂to␈α⊂computing␈α∂with
␈↓ ↓H␈↓algebraic␈α⊂expressions.␈α⊂ The␈α⊂paper␈α⊂had␈α⊂no␈α⊂influence␈α⊂on␈α⊂recursive␈α⊂function␈α⊂theorists,␈α⊂because␈α∂it
␈↓ ↓H␈↓didn't address the questions that interested them.

␈↓ ↓H␈↓␈↓ α_One␈α_mathematical␈α_consideration␈α↔that␈α_influenced␈α_LISP␈α↔was␈α_to␈α_express␈α_programs␈α↔as
␈↓ ↓H␈↓applicative␈α⊂expressions␈α∂built␈α⊂up␈α∂from␈α⊂variables␈α⊂and␈α∂constants␈α⊂using␈α∂functions.␈α⊂ I␈α⊂considered␈α∂it
␈↓ ↓H␈↓important␈α∞to␈α∞make␈α∂these␈α∞expressions␈α∞obey␈α∞the␈α∂usual␈α∞mathematical␈α∞laws␈α∞allowing␈α∂replacement␈α∞of
␈↓ ↓H␈↓expressions␈αby␈αexpressions␈α
giving␈αthe␈αsame␈α
value.␈α The␈αmotive␈αwas␈α
to␈αallow␈αproofs␈α
of␈αproperties
␈↓ ↓H␈↓of␈αprograms␈αusing␈αordinary␈αmathematical␈αmethods.␈α This␈αis␈αonly␈αpossible␈αto␈αthe␈αextent␈αthat␈αside-
␈↓ ↓H␈↓effects␈α_can␈α→be␈α_avoided.␈α_ Unfortunately,␈α→side-effects␈α_are␈α_often␈α→a␈α_great␈α→convenience␈α_when
␈↓ ↓H␈↓computational␈α∩efficiency␈α∪is␈α∩important,␈α∩and␈α∪"functions"␈α∩with␈α∩side-effects␈α∪are␈α∩present␈α∪in␈α∩LISP.
␈↓ ↓H␈↓However,␈α
the␈αso-called␈α
pure␈α
LISP␈αis␈α
free␈αof␈α
side-effects,␈α
and␈α(Cartwright␈α
1976)␈α
and␈α(Cartwright
␈↓ ↓H␈↓and␈α
McCarthy␈α
1978)␈α
show␈α
how␈α
to␈α∞represent␈α
pure␈α
LISP␈α
programs␈α
by␈α
sentences␈α
and␈α∞schemata␈α
in
␈↓ ↓H␈↓first␈αorder␈αlogic␈αand␈αprove␈αtheir␈αproperties.␈α This␈αis␈αan␈αadditional␈αvindication␈αof␈αthe␈αstriving␈αfor
␈↓ ↓H␈↓mathematical␈α⊂neatness,␈α∂because␈α⊂it␈α∂is␈α⊂now␈α⊂easier␈α∂to␈α⊂prove␈α∂that␈α⊂pure␈α∂LISP␈α⊂programs␈α⊂meet␈α∂their
␈↓ ↓H␈↓specifications␈α∂than␈α∂it␈α∂is␈α∞for␈α∂any␈α∂other␈α∂programming␈α∂language␈α∞in␈α∂extensive␈α∂use.␈α∂ (Fans␈α∂of␈α∞other
␈↓ ↓H␈↓␈↓ εH␈↓ 96


␈↓ ↓H␈↓programming␈αlanguages␈αare␈αchallenged␈αto␈αwrite␈αa␈αprogram␈αto␈αconcatenate␈αlists␈αand␈αprove␈αthat␈αthe
␈↓ ↓H␈↓operation is associative).

␈↓ ↓H␈↓␈↓ α_Another␈αway␈αto␈αshow␈αthat␈αLISP␈αwas␈αneater␈αthan␈αTuring␈αmachines␈αwas␈αto␈αwrite␈αa␈αuniversal
␈↓ ↓H␈↓LISP␈α∂function␈α∂and␈α∂show␈α∂that␈α∞it␈α∂is␈α∂briefer␈α∂and␈α∂more␈α∞comprehensible␈α∂than␈α∂the␈α∂description␈α∂of␈α∞a
␈↓ ↓H␈↓universal␈αTuring␈αmachine.␈α This␈αwas␈αthe␈αLISP␈αfunction␈α␈↓↓eval[e,a]␈↓,␈αwhich␈αcomputes␈αthe␈αvalue␈αof␈αa
␈↓ ↓H␈↓LISP␈α
expression␈α
␈↓↓e␈↓␈α
-␈α
the␈α
second␈α
argument␈α
␈↓↓a␈↓␈α
being␈α
a␈α
list␈α
of␈α
assignments␈α
of␈α
values␈α
to␈α
variables.␈α
 (␈↓↓a␈↓␈α
is
␈↓ ↓H␈↓needed␈α⊂to␈α∂make␈α⊂the␈α∂recursion␈α⊂work).␈α⊂ Writing␈α∂␈↓↓eval␈↓␈α⊂required␈α∂inventing␈α⊂a␈α⊂notation␈α∂representing
␈↓ ↓H␈↓LISP␈α
functions␈αas␈α
LISP␈αdata,␈α
and␈αsuch␈α
a␈αnotation␈α
was␈αdevised␈α
for␈αthe␈α
purposes␈αof␈α
the␈αpaper␈α
with
␈↓ ↓H␈↓no␈α∂thought␈α∂that␈α∂it␈α∞would␈α∂be␈α∂used␈α∂to␈α∂express␈α∞LISP␈α∂programs␈α∂in␈α∂practice.␈α∂ Logical␈α∞completeness
␈↓ ↓H␈↓required␈αthat␈αthe␈αnotation␈αused␈αto␈αexpress␈αfunctions␈αused␈αas␈αfunctional␈αarguments␈αbe␈αextended␈αto
␈↓ ↓H␈↓provide␈α
for␈α
recursive␈α
functions,␈α
and␈α∞the␈α
LABEL␈α
notation␈α
was␈α
invented␈α
by␈α∞Nathaniel␈α
Rochester
␈↓ ↓H␈↓for␈αthat␈α
purpose.␈α D.M.R.␈α
Park␈αpointed␈αout␈α
that␈αLABEL␈α
was␈αlogically␈α
unnecessary␈αsince␈αthe␈α
result
␈↓ ↓H␈↓could␈α
be␈α
achieved␈α
using␈α∞only␈α
LAMBDA␈α
-␈α
by␈α∞a␈α
construction␈α
analogous␈α
to␈α∞Church's␈α
␈↓↓Y␈↓-operator,
␈↓ ↓H␈↓albeit in a more complicated way.

␈↓ ↓H␈↓␈↓ α_S.R.␈αRussell␈αnoticed␈αthat␈α␈↓↓eval␈↓␈αcould␈αserve␈αas␈αan␈αinterpreter␈αfor␈αLISP,␈αpromptly␈αhand␈αcoded
␈↓ ↓H␈↓it, and we now had a programming language with an interpreter.

␈↓ ↓H␈↓␈↓ α_The␈α∞unexpected␈α∂appearance␈α∞of␈α∞an␈α∂interpreter␈α∞tended␈α∂to␈α∞freeze␈α∞the␈α∂form␈α∞of␈α∂the␈α∞language,
␈↓ ↓H␈↓and␈αsome␈αof␈αthe␈αdecisions␈αmade␈αrather␈αlightheartedly␈αfor␈αthe␈α"Recursive␈αfunctions␈α..."␈α
paper␈αlater
␈↓ ↓H␈↓proved␈αunfortunate.␈α These␈αincluded␈αthe␈αCOND␈αnotation␈αfor␈αconditional␈αexpressions␈αwhich␈αleads
␈↓ ↓H␈↓to␈αan␈αunnecessary␈αdepth␈αof␈αparentheses,␈αand␈αthe␈α
use␈αof␈αthe␈αnumber␈αzero␈αto␈αdenote␈αthe␈α
empty␈αlist
␈↓ ↓H␈↓NIL␈αand␈αthe␈αtruth␈αvalue␈α␈↓αfalse␈↓.␈α Besides␈αencouraging␈αpornographic␈αprogramming,␈αgiving␈αa␈αspecial
␈↓ ↓H␈↓interpretation to the address 0 has caused difficulties in all subsequent implementations.

␈↓ ↓H␈↓␈↓ α_Another␈αreason␈αfor␈αthe␈αinitial␈αacceptance␈αof␈αawkwardnesses␈αin␈αthe␈αinternal␈αform␈αof␈αLISP␈αis
␈↓ ↓H␈↓that␈α∞we␈α
still␈α∞expected␈α
to␈α∞switch␈α∞to␈α
writing␈α∞programs␈α
as␈α∞M-expressions.␈α
 The␈α∞project␈α∞of␈α
defining
␈↓ ↓H␈↓M-expressions␈α
precisely␈α∞and␈α
compiling␈α∞them␈α
or␈α
at␈α∞least␈α
translating␈α∞them␈α
into␈α∞S-expressions␈α
was
␈↓ ↓H␈↓neither␈α
finalized␈α
nor␈α
explicitly␈αabandoned.␈α
 It␈α
just␈α
receded␈α
into␈αthe␈α
indefinite␈α
future,␈α
and␈α
a␈αnew
␈↓ ↓H␈↓generation␈αof␈αprogrammers␈αappeared␈αwho␈α
preferred␈αinternal␈αnotation␈αto␈αany␈α
FORTRAN-like␈αor
␈↓ ↓H␈↓ALGOL-like notation that could be devised.

␈↓ ↓H␈↓3. From LISP I to LISP 1.5.

␈↓ ↓H␈↓␈↓ α_a.␈αProperty␈αlists.␈α The␈αidea␈αof␈αproviding␈αeach␈αatom␈αwith␈αa␈αlist␈αof␈αproperties␈αwas␈αpresent␈αin
␈↓ ↓H␈↓the␈αfirst␈αassembly␈αlanguage␈αimplementation.␈α
 It␈αwas␈αalso␈αone␈αof␈α
the␈αtheoretical␈αideas␈αof␈αthe␈α
Advice
␈↓ ↓H␈↓Taker,␈αalthough␈αthe␈αAdvice␈αTaker␈α(McCarthy␈α1959)␈αwould␈αhave␈αrequired␈αa␈αproperty␈αlist␈αfor␈αany
␈↓ ↓H␈↓expression␈α⊃about␈α⊃which␈α⊃information␈α⊃was␈α⊃known␈α⊃that␈α⊃did␈α⊃not␈α⊃follow␈α⊃from␈α⊃its␈α∩structure.␈α⊃ The
␈↓ ↓H␈↓READ␈α
and␈α
PRINT␈α
programs␈α
required␈α
that␈α
the␈α
print␈α
names␈α
of␈α
atoms␈α
be␈α
accessible,␈α
and␈α
as␈α
soon␈α
as
␈↓ ↓H␈↓function␈αdefinition␈αbecame␈αpossible,␈αit␈αwas␈αnecessary␈αto␈αindicate␈αwhether␈αa␈αfunction␈αwas␈αa␈αSUBR
␈↓ ↓H␈↓in␈α∞machine␈α
code␈α∞or␈α
was␈α∞an␈α
EXPR␈α∞represented␈α
by␈α∞list␈α
structure.␈α∞ Several␈α
functions␈α∞dealing␈α
with
␈↓ ↓H␈↓property lists were also made available for application programs which made heavy use of them.

␈↓ ↓H␈↓␈↓ α_b.␈αInsertion␈α
of␈αelements␈αin␈α
lists␈αand␈α
their␈αdeletion.␈α One␈α
of␈αthe␈α
original␈αadvertised␈αvirtues␈α
of
␈↓ ↓H␈↓list␈α∞processing␈α
for␈α∞AI␈α∞work␈α
was␈α∞the␈α
ability␈α∞to␈α∞insert␈α
and␈α∞delete␈α
elements␈α∞of␈α∞lists.␈α
 Unfortunately,
␈↓ ↓H␈↓this␈α⊃facility␈α⊃coexists␈α⊃uneasily␈α⊂with␈α⊃shared␈α⊃list␈α⊃structure.␈α⊂ Moreover,␈α⊃operations␈α⊃that␈α⊃insert␈α⊂and
␈↓ ↓H␈↓delete␈α⊂don't␈α⊂have␈α⊂a␈α⊂neat␈α⊂representation␈α⊂as␈α∂functions.␈α⊂ LISP␈α⊂contains␈α⊂them␈α⊂in␈α⊂the␈α⊂form␈α⊂of␈α∂the
␈↓ ↓H␈↓␈↓ εH␈↓ 97


␈↓ ↓H␈↓␈↓↓rplaca␈↓␈α⊗and␈α↔␈↓↓rplacd␈↓␈α⊗pseudo-functions,␈α⊗but␈α↔programs␈α⊗that␈α⊗use␈α↔them␈α⊗cannot␈α↔be␈α⊗conveniently
␈↓ ↓H␈↓represented␈α∞in␈α∞logic,␈α∞because,␈α∞regarded␈α∞as␈α∞functions,␈α∞they␈α∞don't␈α∞permit␈α∞replacement␈α∞of␈α∞equals␈α
by
␈↓ ↓H␈↓equals.

␈↓ ↓H␈↓␈↓ α_c.␈α
Numbers.␈α
 Many␈α
computations␈α
require␈α
both␈α
numbers␈α
and␈α
symbolic␈αexpressions.␈α
 Numbers
␈↓ ↓H␈↓were␈αoriginally␈αimplemented␈αin␈αLISP␈αI␈αas␈αlists␈αof␈αatoms,␈αand␈αthis␈αproved␈αtoo␈αslow␈αfor␈αall␈α
but␈αthe
␈↓ ↓H␈↓simplest␈α∃computations.␈α∃ A␈α⊗reasonably␈α∃efficient␈α∃implementation␈α∃of␈α⊗numbers␈α∃as␈α∃atoms␈α⊗in␈α∃S-
␈↓ ↓H␈↓expressions␈α
was␈α
made␈αin␈α
LISP␈α
1.5,␈α
but␈αin␈α
all␈α
the␈α
early␈αLISPs,␈α
numerical␈α
computations␈α
were␈αstill␈α
10
␈↓ ↓H␈↓to␈α100␈αtimes␈αslower␈αthan␈αin␈αFORTRAN.␈α Efficient␈αnumerical␈αcomputation␈αrequires␈αsome␈αform␈αof
␈↓ ↓H␈↓typing␈α∞in␈α∞the␈α∞source␈α∞language␈α∞and␈α∞a␈α∞distinction␈α∞between␈α∞numbers␈α∞treated␈α∞by␈α∞themselves␈α∞and␈α
as
␈↓ ↓H␈↓elements␈α∞of␈α∞S-expressions.␈α∞ Some␈α∞recent␈α∞versions␈α∞of␈α∞LISP␈α∞allow␈α∞distinguishing␈α∞types,␈α∞but␈α∞at␈α∞the
␈↓ ↓H␈↓time, this seemed incompatible with other features.

␈↓ ↓H␈↓␈↓ α_d.␈α∪Free␈α∪variables.␈α∪ In␈α∩all␈α∪innocence,␈α∪James␈α∪R.␈α∩Slagle␈α∪programmed␈α∪the␈α∪following␈α∩LISP
␈↓ ↓H␈↓function definition and complained when it didn't work right:

␈↓ ↓H␈↓␈↓ α_␈↓↓testr[x,p,f,u]␈α∪←␈α∀␈↓αif␈↓↓␈α∪p[x]␈α∪␈↓αthen␈↓↓␈α∀f[x]␈α∪␈↓αelse␈↓↓␈α∪␈↓αif␈↓↓␈α∀␈↓αat␈↓↓␈α∪x␈α∪␈↓αthen␈↓↓␈α∀u[]␈α∪␈↓αelse␈↓↓␈α∀testr[␈↓αd␈↓↓␈α∪u,p,f,λ:testr[␈↓αd␈↓↓
␈↓ ↓H␈↓↓u,p,f,u]]␈↓.

␈↓ ↓H␈↓The␈αobject␈αof␈αthe␈αfunction␈αis␈αto␈αfind␈αa␈αsubexpression␈αof␈α␈↓↓x␈↓␈αsatisfying␈α␈↓↓p[x]␈↓␈αand␈αreturn␈α␈↓↓f[x].␈↓␈α If␈αthe
␈↓ ↓H␈↓search␈αis␈αunsuccessful,␈αthen␈αthe␈αcontinuation␈αfunction␈α␈↓↓u[]␈↓␈αof␈αno␈αarguments␈αis␈αto␈αbe␈αcomputed␈αand
␈↓ ↓H␈↓its␈α∂value␈α⊂returned.␈α∂ The␈α∂difficulty␈α⊂was␈α∂that␈α∂when␈α⊂an␈α∂inner␈α∂recursion␈α⊂occurred,␈α∂the␈α∂value␈α⊂of␈α∂␈↓↓u␈↓
␈↓ ↓H␈↓wanted␈α
was␈α
the␈αouter␈α
value,␈α
but␈α
the␈αinner␈α
value␈α
was␈α
actually␈αused.␈α
 In␈α
modern␈αterminology,␈α
lexical
␈↓ ↓H␈↓scoping was wanted, and dynamic scoping was obtained.

␈↓ ↓H␈↓␈↓ α_I␈α
must␈α∞confess␈α
that␈α
I␈α∞regarded␈α
this␈α
difficulty␈α∞as␈α
just␈α
a␈α∞bug␈α
and␈α
expressed␈α∞confidence␈α
that
␈↓ ↓H␈↓Steve␈α
Russell␈α
would␈α
soon␈α
fix␈α∞it.␈α
 He␈α
did␈α
fix␈α
it␈α∞but␈α
by␈α
inventing␈α
the␈α
so-called␈α∞FUNARG␈α
device
␈↓ ↓H␈↓that␈α∞took␈α∞the␈α∞lexical␈α∞environment␈α∞along␈α∞with␈α∞the␈α∞functional␈α∞argument.␈α∞ Similar␈α∞difficulties␈α
later
␈↓ ↓H␈↓showed␈αup␈α
in␈αAlgol␈α60,␈α
and␈αRussell's␈αturned␈α
out␈αto␈αbe␈α
one␈αof␈αthe␈α
more␈αcomprehensive␈αsolutions␈α
to
␈↓ ↓H␈↓the␈α∞problem.␈α
 While␈α∞it␈α∞worked␈α
well␈α∞in␈α∞the␈α
interpreter,␈α∞comprehensiveness␈α∞and␈α
speed␈α∞seem␈α∞to␈α
be
␈↓ ↓H␈↓opposed␈α
in␈α
compiled␈α
code,␈α
and␈α
this␈α
led␈αto␈α
a␈α
succession␈α
of␈α
compromises.␈α
 Unfortunately,␈α
time␈αdid
␈↓ ↓H␈↓not␈α∞permit␈α∞writing␈α∞an␈α∞appendix␈α
giving␈α∞the␈α∞history␈α∞of␈α∞the␈α
problem,␈α∞and␈α∞the␈α∞interested␈α∞reader␈α
is
␈↓ ↓H␈↓referred␈αto␈α(Moses␈α1970)␈αas␈αa␈αplace␈αto␈αstart.␈α (David␈αPark␈αtells␈αme␈αthat␈αPatrick␈αFischer␈αalso␈αhad␈αa
␈↓ ↓H␈↓hand in developing the FUNARG device).

␈↓ ↓H␈↓␈↓ α_e.␈α∂The␈α∂"program␈α∂feature".␈α⊂ Besides␈α∂composition␈α∂of␈α∂functions␈α∂and␈α⊂conditional␈α∂expressions,
␈↓ ↓H␈↓LISP␈αalso␈α
allows␈αsequential␈α
programs␈αwritten␈α
with␈αassignment␈α
statements␈αand␈α
␈↓αgo to␈↓s.␈α Compared
␈↓ ↓H␈↓to␈α∞the␈α
mathematically␈α∞elegant␈α∞recursive␈α
function␈α∞definition␈α∞features,␈α
the␈α∞"program␈α∞feature"␈α
looks
␈↓ ↓H␈↓like␈α∞a␈α∞hasty␈α∞afterthought.␈α∞ This␈α∞is␈α∞not␈α∞quite␈α∞correct;␈α∞the␈α∞idea␈α∞of␈α∞having␈α∞sequential␈α∞programs␈α∞in
␈↓ ↓H␈↓LISP␈α
antedates␈α
that␈αof␈α
having␈α
recursive␈αfunction␈α
definition.␈α
 However,␈αthe␈α
notation␈α
LISP␈αuses␈α
for
␈↓ ↓H␈↓PROGs was definitely an afterthought and is far from optimal.

␈↓ ↓H␈↓␈↓ α_f.␈αOnce␈α
the␈α␈↓↓eval␈↓␈α
interpreter␈αwas␈α
programmed,␈αit␈α
became␈αavailable␈α
to␈αthe␈α
programmer,␈αand␈α
it
␈↓ ↓H␈↓was␈α∩especially␈α∩easy␈α∩to␈α∩use␈α∩because␈α∩it␈α⊃interprets␈α∩LISP␈α∩programs␈α∩expressed␈α∩as␈α∩LISP␈α∩data.␈α⊃ In
␈↓ ↓H␈↓particular,␈α∞␈↓↓eval␈↓␈α
made␈α∞possible␈α
FEXPRS␈α∞and␈α
FSUBRS␈α∞which␈α
are␈α∞"functions"␈α
that␈α∞are␈α∞not␈α
given
␈↓ ↓H␈↓their␈αactual␈αarguments␈αbut␈αare␈α
given␈αthe␈αexpressions␈αthat␈αevaluate␈α
to␈αthe␈αarguments␈αand␈αmust␈α
call
␈↓ ↓H␈↓␈↓↓eval␈↓␈α
themselves␈α
when␈α
they␈α
want␈α
the␈α
expressions␈α
evaluated.␈α
 The␈α
main␈α
application␈α
of␈α
this␈α
facility␈α
is
␈↓ ↓H␈↓to␈α∞functions␈α
that␈α∞don't␈α
always␈α∞evaluate␈α
all␈α∞of␈α
their␈α∞arguments;␈α
they␈α∞evaluate␈α
some␈α∞of␈α∞them␈α
first,
␈↓ ↓H␈↓␈↓ εH␈↓ 98


␈↓ ↓H␈↓and␈α∂then␈α∂decide␈α⊂which␈α∂others␈α∂to␈α⊂evaluate.␈α∂ This␈α∂facility␈α⊂resembles␈α∂Algol's␈α∂␈↓↓call-by-name␈↓␈α⊂but␈α∂is
␈↓ ↓H␈↓more␈α∞flexible,␈α∞because␈α∞␈↓↓eval␈↓␈α∞is␈α∞explicitly␈α
available.␈α∞ A␈α∞first␈α∞order␈α∞logic␈α∞treatment␈α∞of␈α
"extensional"
␈↓ ↓H␈↓FEXPRs and FSUBRs now seems possible.

␈↓ ↓H␈↓␈↓ α_g.␈αSince␈αLISP␈α
works␈αwith␈αlists,␈αit␈α
was␈αalso␈αconvenient␈αto␈α
provide␈αfor␈αfunctions␈αwith␈α
variable
␈↓ ↓H␈↓numbers␈α⊃of␈α⊃arguments␈α⊃by␈α⊃supplying␈α⊃them␈α⊃with␈α⊃a␈α⊃list␈α⊃of␈α⊃arguments␈α⊃rather␈α⊃than␈α∩the␈α⊃separate
␈↓ ↓H␈↓arguments.

␈↓ ↓H␈↓␈↓ α_Unfortunately,␈α∩none␈α∩of␈α∩the␈α∩above␈α∩features␈α∩has␈α∩been␈α∩given␈α∩a␈α∩comprehensive␈α∪and␈α∩clear
␈↓ ↓H␈↓mathematical␈α
semantics␈αin␈α
connection␈αwith␈α
LISP␈α
or␈αany␈α
other␈αprogramming␈α
language.␈α
 The␈αbest
␈↓ ↓H␈↓attempt in connection with LISP is Michael Gordon's (1973), but it is too complicated.

␈↓ ↓H␈↓␈↓ α_h.␈αThe␈αfirst␈αattempt␈αat␈αa␈αcompiler␈α
was␈αmade␈αby␈αRobert␈αBrayton,␈αbut␈αwas␈αunsuccessful.␈α
 The
␈↓ ↓H␈↓first␈α∂successful␈α⊂LISP␈α∂compiler␈α∂was␈α⊂programmed␈α∂by␈α⊂Timothy␈α∂Hart␈α∂and␈α⊂Michael␈α∂Levin.␈α⊂ It␈α∂was
␈↓ ↓H␈↓written in LISP and was claimed to be the first compiler written in the language to be compiled.

␈↓ ↓H␈↓␈↓ α_Many␈α∞people␈α
participated␈α∞in␈α∞the␈α
initial␈α∞development␈α∞of␈α
LISP,␈α∞and␈α∞I␈α
haven't␈α∞been␈α∞able␈α
to
␈↓ ↓H␈↓remember␈α⊃all␈α⊃their␈α∩contributions␈α⊃and␈α⊃must␈α⊃settle,␈α∩at␈α⊃this␈α⊃writing,␈α⊃for␈α∩a␈α⊃list␈α⊃of␈α⊃names.␈α∩ I␈α⊃can
␈↓ ↓H␈↓remember␈α∞Paul␈α∞Abrahams,␈α∞Robert␈α∞Brayton,␈α∞Daniel␈α∞Edwards,␈α∞Patrick␈α∞Fischer,␈α∞Phyllis␈α∂Fox,␈α∞Saul
␈↓ ↓H␈↓Goldberg,␈α∞Timothy␈α∞Hart,␈α∞Louis␈α∞Hodes,␈α∂Michael␈α∞Levin,␈α∞David␈α∞Luckham,␈α∞Klim␈α∂Maling,␈α∞Marvin
␈↓ ↓H␈↓Minsky, David Park, Nathaniel Rochester of IBM, and Steve Russell.

␈↓ ↓H␈↓4. Beyond LISP 1.5.

␈↓ ↓H␈↓␈↓ α_As␈αa␈αprogramming␈αlanguage␈αLISP␈αhad␈αmany␈αlimitations.␈α Some␈αof␈αthe␈αmost␈αevident␈αin␈αthe
␈↓ ↓H␈↓early␈α⊂1960s␈α⊂were␈α⊂ultra-slow␈α⊂numerical␈α⊃computation,␈α⊂inability␈α⊂to␈α⊂represent␈α⊂objects␈α⊂by␈α⊃blocks␈α⊂of
␈↓ ↓H␈↓registers␈α
and␈α
garbage␈α
collect␈α
the␈α
blocks,␈α
and␈α
lack␈α
of␈α
a␈α
good␈α
system␈α
for␈α
input-output␈α∞of␈α
symbolic
␈↓ ↓H␈↓expressions␈αin␈αconventional␈αnotations.␈α All␈αthese␈αproblems␈αand␈αothers␈αwere␈αto␈αbe␈αfixed␈αin␈αLISP␈α2.
␈↓ ↓H␈↓In␈αthe␈αmeantime,␈αwe␈αhad␈αto␈αsettle␈αfor␈αLISP␈α1.5␈αdeveloped␈αat␈αM.I.T.␈αwhich␈αcorrected␈αonly␈αthe␈αmost
␈↓ ↓H␈↓glaring deficiencies.

␈↓ ↓H␈↓␈↓ α_The␈α⊗LISP␈α⊗2␈α⊗project␈α⊗was␈α↔a␈α⊗collaboration␈α⊗of␈α⊗Systems␈α⊗Development␈α↔Corporation␈α⊗and
␈↓ ↓H␈↓Information␈α
International␈α
Inc.,␈αand␈α
was␈α
initially␈αplanned␈α
for␈α
the␈αQ32␈α
computer,␈α
which␈α
was␈αbuilt
␈↓ ↓H␈↓by␈α
IBM␈α
for␈αmilitary␈α
purposes␈α
and␈αwhich␈α
had␈α
a␈α48␈α
bit␈α
word␈αand␈α
18␈α
bit␈αaddresses,␈α
i.e.,␈α
it␈αwas␈α
better
␈↓ ↓H␈↓than␈α
the␈α
IBM␈α
7090␈α
for␈α
an␈α
ambitious␈α
project.␈α
 Unfortunately,␈α
the␈α
Q32␈α
at␈α
SDC␈α
was␈αnever␈α
equipped
␈↓ ↓H␈↓with␈α∞more␈α∞than␈α∞48K␈α∞words␈α∞of␈α∞this␈α∞memory.␈α
 When␈α∞it␈α∞became␈α∞clear␈α∞that␈α∞the␈α∞Q32␈α∞had␈α∞too␈α
little
␈↓ ↓H␈↓memory,␈αit␈α
was␈αdecided␈αto␈α
develop␈αthe␈αlanguage␈α
for␈αthe␈αIBM␈α
360/67␈αand␈αthe␈α
Digital␈αEquipment
␈↓ ↓H␈↓PDP-6␈α-␈αSDC␈αwas␈αacquiring␈αthe␈αformer,␈αwhile␈αIII␈αand␈αM.I.T.␈α and␈αStanford␈αpreferred␈αthe␈αlatter.
␈↓ ↓H␈↓The␈α
project␈α
proved␈α
more␈α
expensive␈α
than␈α
expected,␈α
the␈α
collaboration␈α
proved␈α
more␈α
difficult␈αthan
␈↓ ↓H␈↓expected,␈αand␈αso␈αLISP␈α2␈αwas␈αdropped.␈α From␈αa␈α1970s␈αpoint␈αof␈αview,␈αthis␈αwas␈αregrettable,␈αbecause
␈↓ ↓H␈↓much␈α
more␈α
money␈α
has␈α
since␈α
been␈α
spent␈α
to␈α
develop␈α
LISPs␈α
with␈α
fewer␈α
features.␈α
 However,␈α
it␈α
was
␈↓ ↓H␈↓not␈αthen␈αknown␈αthat␈αthe␈αdominant␈αmachine␈αfor␈αAI␈αresearch␈αwould␈αbe␈αthe␈αPDP-10,␈αa␈αsuccessor␈αof
␈↓ ↓H␈↓the␈α⊃PDP-6.␈α⊃ A␈α⊃part␈α⊃of␈α⊃the␈α⊃AI␈α⊃community,␈α∩e.g.␈α⊃BBN␈α⊃and␈α⊃SRI␈α⊃made␈α⊃what␈α⊃proved␈α⊃to␈α∩be␈α⊃an
␈↓ ↓H␈↓architectural digression in doing AI work on the SDS 940 computer.

␈↓ ↓H␈↓␈↓ α_The␈α
existence␈α
of␈αan␈α
interpreter␈α
and␈αthe␈α
absence␈α
of␈αdeclarations␈α
makes␈α
it␈αparticularly␈α
natural
␈↓ ↓H␈↓to␈α
use␈α
LISP␈α
in␈α
a␈α
time-sharing␈α
environment.␈α It␈α
is␈α
convenient␈α
to␈α
define␈α
functions,␈α
test␈α
them,␈αand
␈↓ ↓H␈↓re-edit␈αthem␈αwithout␈αever␈αleaving␈αthe␈αLISP␈αinterpreter.␈α A␈αdemonstration␈αof␈αLISP␈αin␈αa␈αprototype
␈↓ ↓H␈↓␈↓ εH␈↓ 99


␈↓ ↓H␈↓time-sharing␈α∞environment␈α∞on␈α∞the␈α∞IBM␈α∞704␈α∞was␈α∞made␈α∞in␈α∞1960␈α∞(or␈α∞1961).␈α∞(See␈α∞Appendix␈α∞2).␈α∞ L.
␈↓ ↓H␈↓Peter␈α∞Deutsch␈α∞implemented␈α∞the␈α
first␈α∞interactive␈α∞LISP␈α∞on␈α∞the␈α
PDP-1␈α∞computer␈α∞in␈α∞1963,␈α∞but␈α
the
␈↓ ↓H␈↓PDP-1 had too small a memory for serious symbolic computation.

␈↓ ↓H␈↓␈↓ α_The␈αmost␈αimportant␈αimplementations␈αof␈αLISP␈αproved␈αto␈αbe␈αthose␈αfor␈αthe␈αPDP-6␈αcomputer
␈↓ ↓H␈↓and␈α⊗its␈α⊗successor␈α⊗the␈α∃PDP-10␈α⊗made␈α⊗by␈α⊗the␈α∃Digital␈α⊗Equipment␈α⊗Corporation␈α⊗of␈α∃Maynard,
␈↓ ↓H␈↓Massachusetts.␈α∞ In␈α∂fact,␈α∞the␈α∂half␈α∞word␈α∂instructions␈α∞and␈α∂the␈α∞stack␈α∂instructions␈α∞of␈α∂these␈α∞machines
␈↓ ↓H␈↓were␈αdeveloped␈αwith␈αLISP's␈αrequirements␈αin␈αmind.␈α The␈αearly␈αdevelopment␈αof␈αLISP␈αat␈αM.I.T.␈αfor
␈↓ ↓H␈↓this␈α⊃line␈α⊃of␈α⊃machines␈α⊂and␈α⊃its␈α⊃subsequent␈α⊃development␈α⊂of␈α⊃INTERLISP␈α⊃(nee␈α⊃BBN␈α⊃LISP)␈α⊂and
␈↓ ↓H␈↓MACLISP␈α∪also␈α∪contributed␈α∪to␈α∪making␈α∪these␈α∪machines␈α∪the␈α∪machines␈α∪of␈α∪choice␈α∪for␈α∩artificial
␈↓ ↓H␈↓intelligence␈αresearch.␈α The␈αIBM␈α704␈αLISP␈αwas␈αextended␈αto␈αthe␈αIBM␈α7090␈αand␈αlater␈αled␈αto␈αLISPs
␈↓ ↓H␈↓for the IBM 360 and 370.

␈↓ ↓H␈↓␈↓ α_The␈α∂earliest␈α∂publications␈α∂on␈α∂LISP␈α∂were␈α∂in␈α∂the␈α∂Quarterly␈α∂Progress␈α∂Reports␈α∂of␈α∂the␈α∂M.I.T.
␈↓ ↓H␈↓Research␈α⊃Laboratory␈α⊂of␈α⊃Electronics.␈α⊂ (McCarthy␈α⊃1960)␈α⊂was␈α⊃the␈α⊂first␈α⊃journal␈α⊃publication.␈α⊂ The
␈↓ ↓H␈↓␈↓↓LISP␈α∪Programmer's␈α∩Manual␈↓␈α∪by␈α∩Phyllis␈α∪Fox␈α∪was␈α∩published␈α∪by␈α∩the␈α∪Research␈α∪Laboratory␈α∩of
␈↓ ↓H␈↓Electronics␈αin␈α1960␈αand␈αthe␈α␈↓↓LISP␈α1.5␈αProgrammer's␈αManual␈↓␈αby␈αMcCarthy,␈αLevin,␈αet.␈αal.␈α in␈α
1962
␈↓ ↓H␈↓was␈αpublished␈αby␈αM.I.T.␈αPress.␈α After␈αthe␈αpublication␈αof␈α(McCarthy␈αand␈αLevin␈α1962),␈αmany␈α
LISP
␈↓ ↓H␈↓implementations␈α
were␈α
made␈αfor␈α
numerous␈α
computers.␈α However,␈α
in␈α
contrast␈αto␈α
the␈α
situation␈αwith
␈↓ ↓H␈↓most␈αwidely␈αused␈αprogramming␈αlanguages,␈αno␈α
organization␈αhas␈αever␈αattempted␈αto␈αpropagate␈α
LISP,
␈↓ ↓H␈↓and␈α∂there␈α∞has␈α∂never␈α∂been␈α∞an␈α∂attempt␈α∂at␈α∞agreeing␈α∂on␈α∂a␈α∞standardization,␈α∂although␈α∂recently␈α∞A.C.
␈↓ ↓H␈↓Hearn␈α∂has␈α∂developed␈α∂a␈α∂"standard␈α∞LISP"␈α∂(Marti,␈α∂Hearn,␈α∂Griss␈α∂and␈α∞Griss␈α∂1978)␈α∂that␈α∂runs␈α∂on␈α∞a
␈↓ ↓H␈↓number␈α∞of␈α∞computers␈α∞in␈α∞order␈α∞to␈α∂support␈α∞the␈α∞REDUCE␈α∞system␈α∞for␈α∞computation␈α∂with␈α∞algebraic
␈↓ ↓H␈↓expressions.

␈↓ ↓H␈↓5. Conclusions.

␈↓ ↓H␈↓␈↓ α_LISP␈α⊃is␈α⊂now␈α⊃the␈α⊂second␈α⊃oldest␈α⊂programming␈α⊃language␈α⊂in␈α⊃present␈α⊂widespread␈α⊃use␈α⊂(after
␈↓ ↓H␈↓FORTRAN␈α∩and␈α⊃not␈α∩counting␈α⊃APT,␈α∩which␈α∩isn't␈α⊃used␈α∩for␈α⊃programming␈α∩␈↓↓per␈α⊃se␈↓).␈α∩ It␈α∩owes␈α⊃its
␈↓ ↓H␈↓longevity␈α∪to␈α∩two␈α∪facts.␈α∩First,␈α∪its␈α∩core␈α∪occupies␈α∪some␈α∩kind␈α∪of␈α∩local␈α∪optimum␈α∩in␈α∪the␈α∪space␈α∩of
␈↓ ↓H␈↓programming␈α~languages␈α~given␈α~that␈α~static␈α~friction␈α~discourages␈α~purely␈α~notational␈α~changes.
␈↓ ↓H␈↓Recursive␈αuse␈α
of␈αconditional␈α
expressions,␈αrepresentation␈α
of␈αsymbolic␈α
information␈αexternally␈αby␈α
lists
␈↓ ↓H␈↓and␈α
internally␈α
by␈α
list␈αstructure,␈α
and␈α
representation␈α
of␈α
program␈αin␈α
the␈α
same␈α
way␈α
will␈αprobably␈α
have
␈↓ ↓H␈↓a very long life.

␈↓ ↓H␈↓␈↓ α_Second,␈α∂LISP␈α∂still␈α∂has␈α∂operational␈α∂features␈α∞unmatched␈α∂by␈α∂other␈α∂language␈α∂that␈α∂make␈α∂it␈α∞a
␈↓ ↓H␈↓convenient␈α
vehicle␈αfor␈α
higher␈α
level␈αsystems␈α
for␈α
symbolic␈αcomputation␈α
and␈α
for␈αartificial␈α
intelligence.
␈↓ ↓H␈↓These␈α
include␈α
its␈α
run-time␈α
system␈α
that␈α
give␈α
good␈αaccess␈α
to␈α
the␈α
features␈α
of␈α
the␈α
host␈α
machine␈αand␈α
its
␈↓ ↓H␈↓operating␈α
system,␈α
its␈α
list␈αstructure␈α
internal␈α
language␈α
that␈α
makes␈αit␈α
a␈α
good␈α
target␈α
for␈αcompiling␈α
from
␈↓ ↓H␈↓yet␈α∞higher␈α∞level␈α∞languages,␈α∂its␈α∞compatibility␈α∞with␈α∞systems␈α∂that␈α∞produce␈α∞binary␈α∞or␈α∂assembly␈α∞level
␈↓ ↓H␈↓program,␈α∀and␈α∀the␈α∀availability␈α∀of␈α∀its␈α∪interpreter␈α∀as␈α∀a␈α∀command␈α∀language␈α∀for␈α∀driving␈α∪other
␈↓ ↓H␈↓programs.␈α
 (One␈α
can␈α∞even␈α
conjecture␈α
that␈α
LISP␈α∞owes␈α
its␈α
survival␈α
specifically␈α∞to␈α
the␈α
fact␈α∞that␈α
its
␈↓ ↓H␈↓programs␈α⊃are␈α⊂lists,␈α⊃which␈α⊂everyone,␈α⊃including␈α⊂me,␈α⊃has␈α⊂regarded␈α⊃as␈α⊂a␈α⊃disadvantage.␈α⊂ Proposed
␈↓ ↓H␈↓replacements␈α∞for␈α∞LISP,␈α∞e.g.␈α∞POP-2␈α∞(Burstall␈α∞1968,1971),␈α∞abandoned␈α∞this␈α∞feature␈α∞in␈α∞favor␈α∂of␈α∞an
␈↓ ↓H␈↓Algol-like syntax leaving no target language for higher level systems).

␈↓ ↓H␈↓␈↓ α_LISP␈α∩will␈α∩become␈α∩obsolete␈α∩when␈α∩someone␈α∩makes␈α∩a␈α∩more␈α∩comprehensive␈α∪language␈α∩that
␈↓ ↓H␈↓dominates␈α≠LISP␈α~practically␈α≠and␈α~also␈α≠gives␈α~a␈α≠clear␈α~mathematical␈α≠semantics␈α~to␈α≠a␈α~more
␈↓ ↓H␈↓comprehensive set of features.
␈↓ ↓H␈↓␈↓ εH␈↓ *10


␈↓ ↓H␈↓6. References.

␈↓ ↓H␈↓␈↓αAbrahams,␈αPaul␈αW.␈α␈↓(1963),␈α␈↓Machine␈αverification␈αof␈αmathematical␈αproof,␈α␈↓thesis,␈αMIT␈αComputation
␈↓ ↓H␈↓Center, Cambridge, Mass.

␈↓ ↓H␈↓␈↓αAbrahams,␈αPaul␈α
W.,␈αBarnett,␈αJ.,␈α
et␈αal.,␈α␈↓(1966),␈α
"The␈αLISP␈α2␈α
Programming␈αLanguage␈αand␈α
System",
␈↓ ↓H␈↓␈↓Proceedings of the Fall Joint Computer Conference, ␈↓pp.  661-676.

␈↓ ↓H␈↓␈↓αAbrahams,␈α
Paul␈α
W.␈α
␈↓(1967),␈α∞␈↓LISP␈α
2␈α
Specifications,␈α
␈↓Systems␈α
Development␈α∞Corporation␈α
Technical
␈↓ ↓H␈↓report TM-3417/200/00, Santa Monica, Calif.

␈↓ ↓H␈↓␈↓αAllen, John ␈↓(1978), ␈↓Anatomy of LISP, ␈↓McGraw Hill.

␈↓ ↓H␈↓␈↓αBerkeley,␈α∂Edmund␈α⊂C.␈α∂and␈α∂Daniel␈α⊂Bobrow,␈α∂eds.␈↓␈α∂(1964),␈α⊂␈↓The␈α∂Programming␈α∂Language␈α⊂LISP,␈α∂its
␈↓ ↓H␈↓Operation␈α⊂and␈α⊂Applications␈↓,␈α⊂Information␈α⊂International␈α⊂Incorporated,␈α⊂Cambridge,␈α∂Massachusetts.
␈↓ ↓H␈↓(out of print).

␈↓ ↓H␈↓␈↓αBurstall,␈α∃R.M.,␈α∃J.S.␈α∃Collins␈α∃and␈α∃R.J.␈α∃Popplestone␈α∃␈↓(1968),␈α∃␈↓↓The␈α∃POP-2␈α∃Papers␈↓,␈α∀Edinburgh
␈↓ ↓H␈↓University Press, Edinburgh, Scotland.

␈↓ ↓H␈↓␈↓αBurstall,␈α∂R.M.,␈α⊂J.S.␈α∂Collins␈α∂and␈α⊂R.J.␈α∂Popplestone␈α∂␈↓(1971),␈α⊂␈↓↓Programming␈α∂in␈α⊂POP-2␈↓.␈α∂Edinburgh
␈↓ ↓H␈↓University Press, Edinburgh, Scotland.

␈↓ ↓H␈↓␈↓αCartwright,␈α
Robert␈α
␈↓(1976),␈α
 ␈↓A␈α
practical␈αformal␈α
semantic␈α
definition␈α
and␈α
verification␈α
system␈αfor␈α
typed
␈↓ ↓H␈↓LISP␈↓, Stanford Artificial Intelligence Laboratory technical report AIM-296, Stanford, California.

␈↓ ↓H␈↓␈↓αCartwright,␈α
Robert␈α
and␈α∞John␈α
McCarthy␈↓␈α
(1978)␈α
"Representation␈α∞of␈α
Recursive␈α
Programs␈α∞in␈α
First
␈↓ ↓H␈↓Order␈α∀Logic"␈α∀(to␈α∀be␈α∀published).␈α∀(Draft␈α∀available␈α∀as␈α∀FIRST.NEW[W77,JMC]␈α∀at␈α∀SU-AI␈α∀on
␈↓ ↓H␈↓ARPAnet).

␈↓ ↓H␈↓␈↓αCollins,␈αG.E.␈↓␈α
(1960)␈α"A␈αmethod␈α
for␈αoverlapping␈αand␈α
erasure␈αof␈αlists",␈α
␈↓↓Communications␈αof␈αthe␈α
ACM␈↓,
␈↓ ↓H␈↓Vol. 3, pp. 655-657.

␈↓ ↓H␈↓␈↓αChurch,␈αAlonzo␈α␈↓(1941),␈α␈↓Calculi␈αof␈α
Lambda␈αconversion,␈α␈↓Princeton␈αUniversity␈αPress,␈α
Princeton,␈αNew
␈↓ ↓H␈↓Jersey.

␈↓ ↓H␈↓␈↓αFox, Phyllis (1960) ␈↓LISP I Programmers Manual, ␈↓Internal paper, MIT, Cambridge, Mass.

␈↓ ↓H␈↓␈↓αGordon,␈α∩Michael␈α∩␈↓(1973)␈α∩␈↓Models␈α∩of␈α∩Pure␈α∩LISP␈↓,␈α∩Experimental␈α∩Programming␈α∩Reports:␈α∪No.␈α∩31,
␈↓ ↓H␈↓University of Edinburgh, Edinburgh.

␈↓ ↓H␈↓␈↓αGelernter,␈α⊗H.,␈α∃J.␈α⊗R.␈α∃Hansen,␈α⊗and␈α∃C.␈α⊗L.␈α∃Gerberich␈α⊗␈↓(1960),␈α∃"A␈α⊗FORTRAN-Compiled␈α∃List
␈↓ ↓H␈↓Processing Language", ␈↓Journal of the ACM␈↓, Vol. 7, No. 2, pp. 87-101.

␈↓ ↓H␈↓␈↓αHearn,␈αAnthony␈α␈↓(1967),␈α␈↓REDUCE,␈αa␈αUser-oriented␈αInteractive␈αSystem␈αfor␈αAlgebraic␈α
Simplification,
␈↓ ↓H␈↓␈↓Stanford Artificial Intelligence Laboratory technical report AIM-57, Stanford, California.

␈↓ ↓H␈↓␈↓αHewitt,␈α∪Carl␈α∪␈↓(1971),␈α∪␈↓Description␈α∪and␈α∩theoretical␈α∪analysis␈α∪(using␈α∪schemata)␈α∪of␈α∪PLANNER:␈α∩a
␈↓ ↓H␈↓␈↓ εH␈↓ *11


␈↓ ↓H␈↓language␈α↔for␈α↔proving␈α↔theorems␈α↔and␈α_manipulating␈α↔models␈α↔in␈α↔a␈α↔robot,␈α↔␈↓Ph.D.␈α_Thesis,␈α↔MIT,
␈↓ ↓H␈↓Cambridge, Mass.

␈↓ ↓H␈↓␈↓αMcCarthy,␈α⊂John␈α⊂␈↓(1958)␈α⊂"Programs␈α⊂with␈α⊃common␈α⊂sense",␈α⊂␈↓Proceedings␈α⊂of␈α⊂the␈α⊂Symposium␈α⊃on␈α⊂the
␈↓ ↓H␈↓Mechanization of Thought Processes, ␈↓National Physiology Lab, Teddington, England.

␈↓ ↓H␈↓␈↓αMcCarthy,␈α∂J.,␈α∂Minsky,␈α∂M.,␈α∂et␈α∂al.,␈α∂␈↓(1959a),␈α∂Quarterly␈α∂Progress␈α∂Report␈α∂No.␈α∂52,␈α∂Research␈α∂Lab␈α∞of
␈↓ ↓H␈↓Electronics, MIT, Cambridge, Mass.

␈↓ ↓H␈↓␈↓αMcCarthy,␈α∂J.,␈α∂Minsky,␈α∂M.,␈α∞et␈α∂al.,␈α∂␈↓(1959b),␈α∂Quarterly␈α∂Progress␈α∞Report␈α∂No.␈α∂55,␈α∂Research␈α∂Lab␈α∞of
␈↓ ↓H␈↓Electronics, MIT, Cambridge, Mass.

␈↓ ↓H␈↓␈↓αMcCarthy, John ␈↓(1959c), Letter to the Editor, ␈↓CACM, ␈↓Vol. 2, No. 8.

␈↓ ↓H␈↓␈↓αMcCarthy,␈α∂J.,␈α∂Minsky,␈α∂M.,␈α∂et␈α∂al.,␈α∂␈↓(1960a),␈α∂Quarterly␈α∂Progress␈α∂Report␈α∂No.␈α∂56,␈α∂Research␈α∂Lab␈α∞of
␈↓ ↓H␈↓Electronics, MIT, Cambridge, Mass.

␈↓ ↓H␈↓␈↓αMcCarthy,␈α∞John␈α∞␈↓(1960b),␈α∞"Recursive␈α∞Functions␈α∞of␈α∞Symbolic␈α∞Expressions␈α∞and␈α∞their␈α
Computation
␈↓ ↓H␈↓by Machine, part I",␈↓ CACM, ␈↓Vol. 3, No. 4, pp. 184-195.

␈↓ ↓H␈↓␈↓αMcCarthy,␈αJ.,␈αMinsky,␈αM.,␈α
et␈αal.,␈α␈↓(1962a),␈αQuarterly␈α
Progress␈αReport,␈αResearch␈αLab␈αof␈α
Electronics,
␈↓ ↓H␈↓MIT, Cambridge, Mass.

␈↓ ↓H␈↓␈↓αMcCarthy,␈α∂J.,␈α∂Minsky,␈α∂M.,␈α∞et␈α∂al.,␈α∂␈↓(1962b),␈α∂Quarterly␈α∂Progress␈α∞Report␈α∂No.␈α∂64,␈α∂Research␈α∂Lab␈α∞of
␈↓ ↓H␈↓Electronics, MIT, Cambridge, Mass.

␈↓ ↓H␈↓␈↓αMcCarthy,␈α
John␈α
␈↓(1962c),␈α
␈↓LISP␈α
1.5␈α∞Programmer's␈α
Manual,␈α
␈↓(with␈α
Abrahams,␈α
Edwards,␈α∞Hart,␈α
and
␈↓ ↓H␈↓Levin), MIT Press, Cambridge, Mass.

␈↓ ↓H␈↓␈↓αMcCarthy,␈α∂J.,␈α∂Minsky,␈α∂M.,␈α∂et␈α∂al.,␈α∂␈↓(1963a),␈α∂Quarterly␈α∂Progress␈α∂Report␈α∂No.␈α∂68,␈α∂Research␈α∂Lab␈α∞of
␈↓ ↓H␈↓Electronics, MIT, Cambridge, Mass.

␈↓ ↓H␈↓␈↓αMcCarthy,␈α∂J.,␈α∂Minsky,␈α∂M.,␈α∞et␈α∂al.,␈α∂␈↓(1963b),␈α∂Quarterly␈α∂Progress␈α∞Report␈α∂No.␈α∂69,␈α∂Research␈α∂Lab␈α∞of
␈↓ ↓H␈↓Electronics, MIT, Cambridge, Mass.

␈↓ ↓H␈↓␈↓αMcCarthy,␈α∞John␈↓␈α∂(1963c)␈α∞"A␈α∂Basis␈α∞for␈α∂a␈α∞Mathematical␈α∂Theory␈α∞of␈α∂Computation",␈α∞in␈α∂P.␈α∞Braffort
␈↓ ↓H␈↓and␈αD.␈αHirschberg␈α
(eds.),␈α␈↓Computer␈αProgramming␈αand␈α
Formal␈αSystems␈↓,␈αpp.␈α33-70.␈α
 North-Holland
␈↓ ↓H␈↓Publishing Company, Amsterdam.

␈↓ ↓H␈↓␈↓αMcCarthy,␈αJohn␈α
␈↓(1963d)␈α"Towards␈αa␈α
Mathematical␈αScience␈αof␈α
Computation",␈α␈↓Proceedings␈αof␈α
IFIP
␈↓ ↓H␈↓Congress, Munich 1962␈↓, Amsterdam: North-Holland, pp. 21-28.

␈↓ ↓H␈↓␈↓αMcCarthy,␈α⊂J.,␈α⊂Minsky,␈α⊂M.,␈α⊂et␈α⊂al.,␈α⊂␈↓(1965),␈α⊂Quarterly␈α⊂Progress␈α⊂Report␈α⊂No.␈α⊂76,␈α⊂Research␈α⊂Lab␈α⊂of
␈↓ ↓H␈↓Electronics, MIT, Cambridge, Mass.

␈↓ ↓H␈↓␈↓αMcCarthy,␈α⊂J.,␈α⊂Minsky,␈α⊂M.,␈α⊂et␈α⊂al.,␈α⊂␈↓(1966),␈α⊂Quarterly␈α⊂Progress␈α⊂Report␈α⊂No.␈α⊂80,␈α⊂Research␈α⊂Lab␈α⊂of
␈↓ ↓H␈↓Electronics, MIT, Cambridge, Mass.
␈↓ ↓H␈↓␈↓ εH␈↓ *12


␈↓ ↓H␈↓␈↓αMcCarthy,␈α∂John␈α∂and␈α∂Carolyn␈α∂Talcott␈↓␈α∂(1979)␈α∂␈↓↓LISP␈α∂with␈α∂Proofs␈↓,␈α∂to␈α∂be␈α∂published.␈α∂ Versions␈α∞of
␈↓ ↓H␈↓most chapters are available at the Stanford Artificial Intelligence Laboratory.

␈↓ ↓H␈↓␈↓αMarti,␈αJ.␈αB.,␈αHearn,␈αA.␈αC.,␈αGriss,␈αM.␈αL.and␈αGriss,␈αC.␈α␈↓(1978)␈α␈↓Standard␈αLISP␈αReport,␈α␈↓University␈αof
␈↓ ↓H␈↓Utah Symbolic Computation Group Report No 60, Provo, Utah.

␈↓ ↓H␈↓␈↓αThe␈α∂Mathlab␈α∂Group␈α∂␈↓(1977),␈α∂␈↓MACSYMA␈α∂Reference␈α∂Manual,␈α∂␈↓Laboratory␈α∂for␈α⊂Computer␈α∂Science,
␈↓ ↓H␈↓MIT Version 9, Cambridge, Mass.

␈↓ ↓H␈↓␈↓αMitchell,␈αR.W.␈α␈↓(1964)␈α␈↓LISP␈α2␈αSpecifications␈αProposal,␈α␈↓Stanford␈αArtificial␈αIntelligence␈αLaboratory
␈↓ ↓H␈↓Memo No. 21, Stanford, Calif.

␈↓ ↓H␈↓␈↓αMoon,␈α⊂David␈α⊂A.␈α⊂␈↓(1974),␈α⊂␈↓MACLISP␈α⊂Reference␈α⊂Manual,␈α⊂␈↓Project␈α⊂MAC␈α⊂Technical␈α⊃Report,␈α⊂MIT,
␈↓ ↓H␈↓Cambridge, Mass.

␈↓ ↓H␈↓␈↓αMoses,␈αJoel␈α␈↓(1970)␈α␈↓The␈αfunction␈αof␈αFUNCTION␈αin␈αLISP␈αor␈αwhy␈αthe␈αFUNARG␈αproblem␈αshould␈αbe
␈↓ ↓H␈↓called the environment problem␈↓", M.I.T. Artificial Intelligence Memo 199, Cambridge, Mass.

␈↓ ↓H␈↓␈↓αNewell,␈α
A.,␈α
and␈αJ.C.␈α
Shaw␈α
␈↓(1957)␈α"Programming␈α
the␈α
Logic␈αTheory␈α
Machine",␈α
␈↓Proceedings␈α
of␈αthe
␈↓ ↓H␈↓1957 Western Joint Computer Conference, ␈↓IRE.

␈↓ ↓H␈↓␈↓αRulifson,␈α∃J.␈α∃et␈α∃al.␈α∃␈↓(1968),␈α⊗"QA4␈α∃-␈α∃A␈α∃Language␈α∃for␈α∃Writing␈α⊗Problem-Solving␈α∃Programs",
␈↓ ↓H␈↓␈↓Proceeding IFIP 1968 Congress, ␈↓TA-2, pp 111-115.

␈↓ ↓H␈↓␈↓αStoyan,␈αHerbert␈↓.␈α Herbert␈αStoyan␈αof␈αDresden,␈α
DDR␈αhas␈αcompleted␈αseveral␈αchapters␈αon␈αthe␈α
history
␈↓ ↓H␈↓of LISP.

␈↓ ↓H␈↓␈↓αSussman,␈αG.␈αWinograd,␈αT.,␈αand␈αCharniak,␈αE.␈α␈↓(1970),␈α␈↓Microplanner␈αReference␈αManual,␈α␈↓AI␈αMemo
␈↓ ↓H␈↓203, AIL MIT, Camridge, Mass.

␈↓ ↓H␈↓␈↓αTeitelman,␈α⊂Warren␈α⊃␈↓(1975),␈α⊂␈↓INTERLISP:␈α⊂Interlisp␈α⊃Reference␈α⊂Manual,␈α⊂Xerox␈α⊃PARC␈α⊂Technical
␈↓ ↓H␈↓Report, Palo Alto, Calif.

␈↓ ↓H␈↓␈↓αWeisman, Clark ␈↓(1967), ␈↓LISP 1.5 Primer, ␈↓Dickenson Press.

␈↓ ↓H␈↓Many␈α⊂reports␈α⊃and␈α⊂memoranda␈α⊂of␈α⊃the␈α⊂M.I.T.␈α⊂and␈α⊃Stanford␈α⊂Artificial␈α⊃Intelligence␈α⊂Laboratories
␈↓ ↓H␈↓have dealt with various aspects of LISP and higher level systems built on LISP.

␈↓ ↓H␈↓APPENDIX - HUMOROUS ANECDOTE

␈↓ ↓H␈↓␈↓ α_The␈α
first␈α
on-line␈α
demonstration␈α
of␈α
LISP␈α
was␈α
also␈α
the␈α
first␈α
of␈α
a␈α
precursor␈α
of␈α
time-sharing
␈↓ ↓H␈↓that␈α∀we␈α∪called␈α∀"time-stealing".␈α∪ The␈α∀audience␈α∪comprised␈α∀the␈α∪participants␈α∀in␈α∪one␈α∀of␈α∪M.I.T.'s
␈↓ ↓H␈↓Industrial␈α
Liaison␈α
Symposia␈α
on␈α
whom␈α
it␈α
was␈α
important␈α
to␈α
make␈α
a␈α
good␈α
impression.␈α
 A␈α
Flexowriter
␈↓ ↓H␈↓had␈α∩been␈α⊃connected␈α∩to␈α∩the␈α⊃IBM␈α∩704␈α⊃and␈α∩the␈α∩operating␈α⊃system␈α∩modified␈α⊃so␈α∩that␈α∩it␈α⊃collected
␈↓ ↓H␈↓characters␈α∞from␈α∞the␈α∞Flexowriter␈α∞in␈α∞a␈α∂buffer␈α∞when␈α∞their␈α∞presence␈α∞was␈α∞signalled␈α∞by␈α∂an␈α∞interrupt.
␈↓ ↓H␈↓Whenever␈α↔a␈α↔carriage␈α⊗return␈α↔occurred,␈α↔the␈α⊗line␈α↔was␈α↔given␈α⊗to␈α↔LISP␈α↔for␈α↔processing.␈α⊗ The
␈↓ ↓H␈↓demonstration␈α∞depended␈α∞on␈α∞the␈α∂fact␈α∞that␈α∞the␈α∞memory␈α∞of␈α∂the␈α∞computer␈α∞had␈α∞just␈α∂been␈α∞increased
␈↓ ↓H␈↓from␈α∞8192␈α∞words␈α
to␈α∞32768␈α∞words␈α
so␈α∞that␈α∞batches␈α
could␈α∞be␈α∞collected␈α
that␈α∞presumed␈α∞only␈α∞a␈α
small
␈↓ ↓H␈↓memory.
␈↓ ↓H␈↓␈↓ εH␈↓ *13


␈↓ ↓H␈↓␈↓ α_The␈αdemonstration␈αwas␈αalso␈α
one␈αof␈αthe␈αfirst␈α
to␈αuse␈αclosed␈αcircuit␈α
TV␈αin␈αorder␈αto␈α
spare␈αthe
␈↓ ↓H␈↓spectators␈α
the␈α
museum␈α
feet␈α
consequent␈α
on␈α
crowding␈α
around␈α
a␈α
terminal␈α
waiting␈α
for␈α∞something␈α
to
␈↓ ↓H␈↓happen.␈α∩ Thus␈α∩they␈α∪were␈α∩on␈α∩the␈α∪fourth␈α∩floor,␈α∩and␈α∪I␈α∩was␈α∩in␈α∪the␈α∩first␈α∩floor␈α∪computer␈α∩room
␈↓ ↓H␈↓exercising␈αLISP␈αand␈αspeaking␈αinto␈αa␈α
microphone.␈α The␈αproblem␈αchosen␈αwas␈αto␈αdetermine␈α
whether
␈↓ ↓H␈↓a␈α∃first␈α∃order␈α∃differential␈α∃equation␈α∃of␈α⊗the␈α∃form␈α∃␈↓↓Mdx + Ndy␈↓␈α∃was␈α∃exact␈α∃by␈α⊗testing␈α∃whether
␈↓ ↓H␈↓␈↓↓∂M/∂y = ∂N/∂x␈↓, which also involved some primitive algebraic simplification.

␈↓ ↓H␈↓␈↓ α_Everything␈α
was␈α
going␈α
well,␈α
if␈α
slowly,␈α
when␈α
suddenly␈α
the␈α
Flexowriter␈α
began␈α
to␈α
type␈α∞(at␈α
ten
␈↓ ↓H␈↓characters per second)

␈↓ ↓H␈↓"THE␈α GARBAGE␈α COLLECTOR␈α∨HAS␈α BEEN␈α CALLED.␈α   SOME␈α∨INTERESTING
␈↓ ↓H␈↓STATISTICS ARE AS FOLLOWS:"

␈↓ ↓H␈↓and␈α
on␈αand␈α
on␈α
and␈αon.␈α
 The␈α
garbage␈αcollector␈α
was␈αquite␈α
new␈α
at␈αthe␈α
time,␈α
we␈αwere␈α
rather␈αproud␈α
of
␈↓ ↓H␈↓it␈α∞and␈α∞curious␈α∞about␈α
it,␈α∞and␈α∞our␈α∞normal␈α∞output␈α
was␈α∞on␈α∞a␈α∞line␈α∞printer,␈α
so␈α∞it␈α∞printed␈α∞a␈α∞full␈α
page
␈↓ ↓H␈↓every␈αtime␈αit␈αwas␈αcalled␈αgiving␈αhow␈αmany␈αwords␈αwere␈αmarked␈αand␈αhow␈αmany␈αwere␈αcollected␈αand
␈↓ ↓H␈↓the␈α
size␈α
of␈α
list␈α∞space,␈α
etc.␈α
 During␈α
a␈α
previous␈α∞rehearsal,␈α
the␈α
garbage␈α
collector␈α
hadn't␈α∞been␈α
called,
␈↓ ↓H␈↓but␈α∩we␈α∪had␈α∩not␈α∪refreshed␈α∩the␈α∩LISP␈α∪core␈α∩image,␈α∪so␈α∩we␈α∩ran␈α∪out␈α∩of␈α∪free␈α∩storage␈α∪during␈α∩the
␈↓ ↓H␈↓demonstration.

␈↓ ↓H␈↓␈↓ α_Nothing␈α∩had␈α∩ever␈α∩been␈α∩said␈α∩about␈α∩a␈α∩garbage␈α∩collector,␈α∩and␈α∩I␈α∩could␈α∩only␈α∩imagine␈α⊃the
␈↓ ↓H␈↓reaction␈α∂of␈α∂the␈α∂audience.␈α∂ We␈α∂were␈α∂already␈α⊂behind␈α∂time␈α∂on␈α∂a␈α∂tight␈α∂schedule,␈α∂it␈α∂was␈α⊂clear␈α∂that
␈↓ ↓H␈↓typing␈α∩out␈α⊃the␈α∩garbage␈α⊃collector␈α∩message␈α∩would␈α⊃take␈α∩all␈α⊃the␈α∩remaining␈α⊃time␈α∩allocated␈α∩to␈α⊃the
␈↓ ↓H␈↓demonstration,␈α∞and␈α∞both␈α∞the␈α∞lecturer␈α∞and␈α∞the␈α∞audience␈α∞were␈α∞incapacitated␈α∞by␈α∞laughter.␈α∂ I␈α∞think
␈↓ ↓H␈↓some of them thought we were victims of a practical joker.